同余方程

同余方程似乎和拓展gcd有关

拓展gcd就是在求ax+by=c的一组解（？）

代码如下：

1 int exgcd(int a,int b,int &x,int &y){
2 　　int t;
3 　　if(!b) {x=1;y=0;return a;}
4 　　t=exgcd(b,a%b,y,x);
5 　　y-=(a/b)*x;
6 　　return t;
7 }

只不过在这个程序里int要换成longlong要不会爆

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 long long exgcd(long long a,long long b,long long &x,long long &y){
 5     long long t;
 6     if(!b) {x=1;y=0;return a;}
 7     t=exgcd(b,a%b,y,x);
 8     y-=(a/b)*x;
 9     return t;
10 }
11 
12 int main(){
13     long long a,b;
14     scanf("%lld%lld",&a,&b);
15     long long x,y;
16     exgcd(a,b,x,y);
17     x=(x%b+b)%b;
18     printf("%lld
",x);
19     return 0;
20 }

数学这东西呀真是……

唉算了不管了

然后是标程……

啊标程代码和zrt大佬的代码几乎一模一样

那么下面是我的枚举大法：

1 int a,b,x;
2 scanf("%d%d",&a,&b);
3 for(int i = 2;;i++){
4     if(((a % b) * (i % b)) % b == 1){
5         x = i;
6         break;
7     }
8 }
9 printf("%d",x);

暴力出奇迹！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

md今天没改题好烦哦