洛谷 P1082 同余方程

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

3 10

输出样例#1：

说明

【数据范围】

对于 40%的数据，2 ≤b≤ 1,000；

对于 60%的数据，2 ≤b≤ 50,000,000；

对于 100%的数据，2 ≤a, b≤ 2,000,000,000。

NOIP 2012 提高组第二天第一题

**************************************************************

 /*

     Problem:

     OJ:

     User:S.B.S.

     Time:

     Memory:

     Length:

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstdlib>

 #include<iomanip>

 #include<cassert>

 #include<climits>

 #include<functional>

 #include<bitset>

 #include<vector>

 #include<list>

 #include<map>

 #define maxn 100001

 #define F(i,j,k) for(int i=j;i<=k;i++)

 #define rep(i,j,k) for(int i=j;i<k;i++)

 #define M(a,b) memset(a,b,sizeof(a))

 #define FF(i,j,k) for(int i=j;i>=k;i--)

 #define inf 0x3f3f3f3f

 #define maxm 1001

 #define mod 998244353

 //#define LOCAL

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 void print(int n){

     if(n<){putchar('-');n=-n;}

     if(n>=) print(n/);

     putchar((n%)+'');

     return;

 }

 int n,m;

 inline int exgcd(int a,int b,int &x,int &y)

 {

     if(!b){x=;y=;return a;}

     int d=exgcd(b,a%b,x,y);

     int temp=x;x=y;y=temp-a/b*y;

     return d;

 }

 int main()

 {

     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;

     #ifdef LOCAL

     freopen("data.in","r",stdin);

     freopen("data.out","w",stdout);

     #endif

     int a,b;cin>>a>>b;

     int x,y;

     exgcd(a,b,x,y);

     x=(x%b+b)%b;

     cout<<x<<endl;

     return ;

 }