「Luogu1082」同余方程

Source and Judge

NOIP2012 提高组 D2T1
Luogu1082
Caioj1554

Problem

「Brief description」

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

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

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

对于 40%的数据,2 ≤b≤ 1,000;

对于 60%的数据,2 ≤b≤ 50,000,000;

对于 100%的数据,2 ≤a, b≤ 2,000,000,000。
「Sample input」

3 10
「Sample output」

7
「Sample explanation」**



Record

10min

Analysis

请先思考后再展开

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
int tx,ty;
int t=exgcd(b,a%b,tx,ty);
x=ty;
y=tx-(a/b)*ty;
return t;
}
int main()
{
int a,b;scanf("%d%d",&a,&b);
int A=a,B=b,K=1;
int x,y;
int gcd=exgcd(A,B,x,y);
x=x*(K/gcd);

int t=B/K;
int XX=(x%t+t)%t;
printf("%d",XX);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ad35.html
转载请注明出处,谢谢!