1265. [NOIP2012] 同余方程
2018-06-18 04:05:06来源:未知 阅读 ()
1265. [NOIP2012] 同余方程
★☆ 输入文件:mod.in
输出文件:mod.out
简单对比
时间限制:1 s 内存限制:128 MB
【题目描述】
求关于 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。
思路:裸扩展欧几里得
错因:其实这个题我应该能写出来,但是因为一开始考试的时候没有看第一页的”12题必须做“,只是想着老师昨天说的四个题里做三个,然后个人认为自己图论比数论牛逼所以上来就奔着后三个题去了,直到最后五分钟才看见这句话无奈只能敲暴力。。。。。。
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:1182. 凸多边形划分
下一篇:1018. 打电话
- 1200 同余方程 2018-06-17
- 【noip 2012】同余方程 2018-06-17
- 线性同余同余方程组解法(excrt) 2018-06-17
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