【noip 2012】同余方程
2018-06-17 21:47:00来源:未知 阅读 ()
题目描述
求关于 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。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 void ex_gcd(int a,int b,int &x,int &y){ 7 if(b==0){x=1,y=0;return;} 8 ex_gcd(b,a%b,x,y); 9 int tmp=x;x=y;y=tmp-(a/b)*y; 10 } 11 int main(){ 12 int a,b,x,y; 13 scanf("%d%d",&a,&b); 14 ex_gcd(a,b,x,y); 15 printf("%d\n",(x+b)%b); 16 return 0; 17 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:【poj 3385】【模板】负环
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【做题笔记】[NOIOJ,非NOIp原题]装箱问题 2020-02-14
- CSP(noip)中的简单对拍写法 2019-10-25
- NOIP模拟day1-T1(完全背包) 2019-10-12
- [NOIP2016]天天爱跑步-题解 2019-10-08
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