扩展gcd codevs 1200 同余方程

codevs 1200 同余方程

2012年NOIP全国联赛提高组

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

3 10 

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

【数据范围】
对于 40%  的数据， 2 ≤b≤ 1,000 ；
对于 60% 的数据， 2 ≤b≤ 50,000,000 
对于 100%  的数据， 2 ≤a, b≤ 2,000,000,000

分类标签 Tags 点此展开 

欧几里德定理 数论 大陆地区 NOIP全国联赛提高组 2012年 1 /* ax ≡ 1 (mod b)就是ax=by+1,而且x，y都为整数，所以ax mod b==1,对于ax=by+1，用扩展gcd求解，再用找到合适的x输出即可*/ 2 #include<iostream> 3 using namespace std; 4 #include<cstdio> 5 long long a,b; 6 void exgcd(long long a,long long b,long long &x,long long &y,long long &gcd) 7 { 8 if(b==0) 9 { 10 gcd=a;x=1;y=0; 11 return; 12 } 13 exgcd(b,a%b,x,y,gcd); 14 int t=x; 15 x=y; 16 y=t-(a/b)*y; 17 } 18 int main() 19 { 20 cin>>a>>b; 21 long long gcd,x,y; 22 exgcd(a,b,x,y,gcd); 23 long long a0=a/gcd,b0=b/gcd; 24 long long k=1/gcd; 25 x*=k;y*=k; 26 if(x<=0) 27 { 28 int i=1; 29 while(1) 30 { 31 if(a*(x+i*b0)+b*(y-i*a0)==1) 32 { 33 if(x+i*b0>0) 34 { 35 cout<<(x+i*b0)<<endl; 36 return 0; 37 } 38 } 39 i++; 40 } 41 } 42 if(x>0) 43 { 44 int i=-1; 45 while(1) 46 { 47 if(a*(x+i*b0)+b*(y-i*a0)==1) 48 { 49 if(x+i*b0<0) 50 { 51 cout<<x<<endl; 52 return 0; 53 } 54 } 55 i--; 56 } 57 } 58 return 0; 59 }

 

转载于:https://www.cnblogs.com/c1299401227/p/5506994.html

总结

以上是生活随笔为你收集整理的扩展gcd codevs 1200 同余方程的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。