Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Lib{
/* Verify
http://codeforces.com/contest/903/submission/33247715
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2647639
*/
/* 参考 http://math314.hateblo.jp/entry/2015/05/07/014908 */
static long extgcd(long a,long b,long[]x) {
for (long u = x[1] = 1, v = x[0] = 0; a!=0;){
long q = b / a;
long r=x[0]-q*u;
x[0]=u;
u=r;
r=x[1]-q*v;
x[1]=v;
v=r;
r=b-q*a;
b=a;
a=r;
}
return b;
}
static long mod_inv(long a,long m) {
long[]x=new long[2];
extgcd(a, m, x);
return (m + x[0] % m) % m;
}
/*
x==a[i] (mod m[i])を満たすxのうち、絶対値最小のものを返す。
事前条件 a.length==m.length
計算量 O(a.length^2)
*/
public static BigInteger garner(long[]a,long[]m){
int ms=a.length;
long[]coffs=new long[ms],constants=new long[ms];
long[]digs=new long[ms];
Arrays.fill(coffs,1);
for(int i=0;i<ms;++i){
long v = (a[i] - constants[i]) * mod_inv(coffs[i], m[i]) % m[i];
if(v<0)v+=m[i];
digs[i]=v;
for (int j = i + 1; j < ms; j++) {
constants[j] += coffs[j] * v;
constants[j] %= m[j];
coffs[j] *= m[i];
coffs[j] %= m[j];
}
}
BigInteger ans=BigInteger.valueOf(0),c=BigInteger.valueOf(1);
for(int i=ms-1;i>=0;--i){
c=c.multiply(BigInteger.valueOf(m[i]));
ans=ans.multiply(BigInteger.valueOf(m[i]));
ans=ans.add(BigInteger.valueOf(digs[i]));
}
if(ans.compareTo(c.divide(BigInteger.valueOf(2)))>0)
ans=ans.subtract(c);
return ans;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.