一本通1632【 例 2】[NOIP2012]同余方程

时间:2024-01-01 14:56:09

1632:【 例 2】[NOIP2012]同余方程

时间限制: 1000 ms         内存限制: 524288 KB

【题目描述】

求关于 x 的同余方程 ax≡1(mod b) 的最小正整数解。

【输入】

输入只有一行,包含两个正整数 a,b,用一个空格隔开。

【输出】

输出只有一行,包含一个正整数 x0 ,即最小正整数解。输入数据保证一定有解。

【输入样例】

3 10

【输出样例】

7

【提示】

数据范围与提示

对于 40% 的数据,有 2≤b≤1000;

对于 60% 的数据,有 2≤b≤50000000;

对于 100% 的数据,有 2≤a,b≤2000000000。

sol:水模板是一件让人快乐的事。。。

原式 Ax=1 (%B)
-->Ax=1+By
-->Ax-By=1
-->Ax+By=1 (类似ax+by=c的格式)
如果1%gcd(A,B)不等于0则无解(显然有解)

然后就是模板了,。。。

Ps:突然发现Exgcd里可以求gcd。。。(貌似我智障了)

/*
原式 Ax=1 (%B)
-->Ax=1+By
-->Ax-By=1
-->Ax+By=1 (类似ax+by=c的格式)
如果1%gcd(A,B)不等于0则无解(显然有解)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
ll A,B;
//Ax+By=1
inline ll gcd(ll x,ll y)
{
return (!y)?(x):(gcd(y,x%y));
}
inline void Exgcd(ll a,ll b,ll &X,ll &Y)
{
if(b==)
{
X=;
Y=;
return;
}
Exgcd(b,a%b,X,Y);
ll XX=X,YY=Y;
X=YY;
Y=XX-a/b*YY;
return;
}
int main()
{
R(A); R(B);
ll a,b,c,r,X,Y;
a=A;
b=B;
c=;
r=gcd(A,B);
Exgcd(a,b,X=,Y=);
X=X*c/r;
ll tmp=b/r;
X=(X>=)?(X%tmp):(X%tmp+tmp);
Wl(X);
return ;
}
/*
input
3 10
output
7
*/