#include<iostream>
using namespace std;
#define maxn 10000 //数的数量
int num[maxn],lef[maxn]; //除数和余数
long long mm[maxn],use[maxn];
//扩展欧几里德求逆元
int extended_euclid(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
int t,d;
d=extended_euclid(b,a%b,x,y);
t=x;
x=y;
y=t-(a/b)*y;
return d;
}
//返回第一个正的解 n为数的数量
long long chinaleft(int n)
{
int i,j,k,x,y;
long long pm,res;
for(i=0,pm=1;i<n;i++)
pm*=num[i];
for(i=0;i<n;i++)
{
mm[i]=pm/num[i];
extended_euclid(mm[i],num[i],x,y);
use[i]=mm[i]*x;
}
for(i=0,res=0;i<n;i++)
res=(res+lef[i]*use[i])%pm;
if(res<0) res+=pm;
return res;
}
这一阵子在狂啃数论,真是不喜欢这种纯数学的东西...马上都要比赛了才刚刚会中国剩余定理...真是丢脸...