1200 同余方程
2018-06-17 22:53:46来源:未知 阅读 ()
1200 同余方程
2012年NOIP全国联赛提高组
求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入只有一行,包含两个正整数 a, b,用 一个 空格隔开。
输出只有一行包含一个正整数x0,即最小正整数解,输入数据保证一定有解。
3 10
7
【数据范围】
对于 40% 的数据, 2 ≤b≤ 1,000 ;
对于 60% 的数据, 2 ≤b≤ 50,000,000
对于 100% 的数据, 2 ≤a, b≤ 2,000,000,000
分类标签 Tags 点此展开
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int x,y; 5 int gcd(int a,int b,int &x,int &y) 6 { 7 if(b==0) 8 { 9 x=1; 10 y=0; 11 return a; 12 } 13 int r=gcd(b,a%b,x,y); 14 int tmp=0; 15 tmp=x; 16 x=y; 17 y=(tmp-(a/b)*y); 18 return r; 19 20 } 21 int main() 22 { 23 int a,b; 24 cin>>a>>b; 25 int r=gcd(a,b,x,y); 26 while(x<0) 27 { 28 x=b+x; 29 } 30 cout<<x; 31 return 0; 32 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 多项式方程的输出 2019-10-16
- [C++] 化学方程式的格式化算法 2018-12-09
- ocrosoft 1015 习题1.22 求一元二次方程a*x^2 + b*x + c = 0 2018-06-21
- 1265. [NOIP2012] 同余方程 2018-06-18
- 实现解一元二次方程(循环) 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash