题目描述

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

本题保证有解

输入格式 一行，包含3个正整数 a , b , c 用一个空格隔开。

输出格式

若干行，从小到大，一行输出一个结果

评测结果： AC 38 ，WA 2 。

Wrong Answer 0Standard answer longer than user output.

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int i,a,b,c,x,y,num[100000001],dep,dt,ans[100000001],an;
signed main(){
   cin>>a>>b>>c;
   dt=__gcd(__gcd(a,b),__gcd(b,c));
   a/=dt;
   b/=dt;
   c/=dt;
   x=a;	
   y=b;
   while(y!=0){		
   	dep++;
   	num[dep]=x/y;
   	swap(x,y);
   	y=y%x;
   }	
   x=1;
   while(dep!=0){
   	swap(x,y);
   	y=y-num[dep]*x;
   	dep--;
   }	
   x*=c;
   y*=c;
   x+=(0-x)/b*b;
   if(x<0)
   	x+=b;
   cout<<x<<endl;
   while(1){
   	i++;
   	if(x+i*b>b)break;
   	cout<<x+i*b<<endl;
   }
}
// ax+by=c;
// 即ax=c(mod b)