【noip 2012】同余方程

2018-06-17 21:47:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:
3 10
输出样例#1:
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】【模板】负环

下一篇:C++中setiosflags()的用法