package yukicoder; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main{ public static void main(String[] args){ new Main().solve(); } long gcd(long t1,long t2){ if(t1 primeList=p.primeList((int)Math.sqrt(MOD)); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); long[] x=new long[n];//x余る long[] y=new long[n];//mod y HashMap map=new HashMap(); /* * HashMap f=p.primeFactorF(primeList, y[i]); for(Factor ff:f){ if(!f.contains(ff.base)) map.put(ff.base, new long[]{ff.exp,x[i]}); else{ if(map.get(ff.base)[0] e:map.entrySet()){ mod[now]=pow(e.getKey(),e.getValue()[0]); X[now]=e.getValue()[1]%mod[now]; now++; } if(hasContradiction(x,y)){ System.out.println(-1); return; } long[] gs=garner(X,mod); long ret=0; for(int i=gs.length-1;i>=0;i--){ ret=(ret*mod[i]+gs[i])%MOD; } System.out.println(ret); } void tr(Object...o){System.out.println(Arrays.deepToString(o));} long pow(long a,long n){ long A=a; long ans=1; while(n>=1){ if(n%2==0){ A=A*A; n/=2; }else if(n%2==1){ ans=ans*A; n--; } } return ans; } long[] garner(long[] x,long[] m){ assert x.length!=m.length; int n=x.length; /** * gamma[i]=(m[0]m[1]...m[i-1])^(-1) mod m[i] */ long[] gamma=new long[n]; for(int i=0;i=0;j--){ tmp=(tmp*m[j]+v[j])%m[i]; } v[i]=(x[i]-tmp)*gamma[i]%m[i]; while(v[i]<0)v[i]+=m[i]; } long[] mods=new long[n]; mods[0]=1; return v; } long inv_pos(long a,long p){ long ans=inverse_element(a,p); while(ans<0)ans+=p; return ans; } /** * Verified * yukicoder No.109 * * ax=1 mod p * となる逆元x=a^(-1)を求める。 * 負の値を返すことがあることに注意。 * a,pが互いに素でないときは逆元は存在しない(正しくない値を返す)。 * 拡張ユークリッドの控除法を用いた。 * */ long inverse_element(long a,long p){ return extended_Euclid(1, 0, a, 0, 1, p)[0]; } /** *拡張ユークリッドの控除法。 *参考 *http://arc360.info/algo/privatekey.html * * extende_Euclid(1,0,a,0,1,b) * が最初に代入する値。 * ax+by=gcd(a,b)を満たす、(x,y)とgcd(a,b)を * {x,y,gcd(a,b)}の形で返す。 */ long[] extended_Euclid(long x0,long y0,long c0,long x1,long y1,long c1){ if(c0 0){ long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p<0 ? p + mod: p; } class Prime{ boolean[] isPrimeArray(int max){ boolean[] isPrime=new boolean[max+1]; Arrays.fill(isPrime, true); isPrime[0]=isPrime[1]=false; for(int i=2;i*i<=max;i++){ if(isPrime[i]){ for(int j=2;j*i<=max;j++){ isPrime[j*i]=false; } } } return isPrime; } /* * max以下の素数のリストを返す */ ArrayList primeList(int max){ boolean[] isPrime=isPrimeArray(max); ArrayList primeList=new ArrayList(); for(int i=2;i<=max;i++){ if(isPrime[i]){ primeList.add(i); } } return primeList; } /* * numをprimeListの素数をもとに素因数分解し、因数を * ArrayListの形で返す。 * primeListにはnumの平方根以下の素数が含まれていなければならない。 * */ ArrayList primeFactorF(ArrayList primeList,long num){ ArrayList ret=new ArrayList(); for(int p:primeList){ int exp=0; while(num%p==0){ num/=p; exp++; } if(exp>0)ret.add(new Factor(p,exp)); } if(num>1)ret.add(new Factor((int)num,1)); return ret; } } class Factor{ long base,exp; Factor(long base,long exp){ this.base=base; this.exp=exp; } } class Pair{ long x; long mod; Pair(long x,long mod){ this.x=x; this.mod=mod; } } }