2014
03-23

# The lastest Math theory problem

There is a positive integer N,satisfied that (N / a1) equals K1a1, (N / a2) equals K2a2 and so on. Then, I want you to tell me the smallest N.

Input is a integer n(1<=n<=6), then n numbers ai (16 < ai < 10000 )described above.

Input is a integer n(1<=n<=6), then n numbers ai (16 < ai < 10000 )described above.

1
323
2
17 19

323
3493625

#include<cstdio>
#include<cstring>
#define ll __int64
ll M=19880502ll,A[6],B[6][9999];
int n,v[9999];
ll gcd(ll a,ll b)
{
if(!b)return a;
return gcd(b,a%b);
}
ll egcd(ll a,ll b,ll &x,ll &y)
{
if(!b){x=1;y=0;return a;}
ll d=egcd(b,a%b,x,y),t=x;
x=y;
y=t-a/b*y;
return d;
}
ll Pow(ll a,ll b)
{
ll r=1;
while(b)
{
if(b&1)r=r*a%M;
a=a*a%M;
b>>=1;
}
return r;
}
ll sol(int k)
{
ll x,y,t=B[0][k],m=A[0];
for(int i=1;i<n;i++)
{
ll d=egcd(m,A[i],x,y),tp=B[i][k]-t;
if(tp%d!=0)return -1;
x=tp/d*x%A[i];
if(x<0)x+=A[i];
t=x*m+t;
m=m/gcd(m,A[i])*A[i];
}
return t%m;
}
int main()
{
while(~scanf("%d",&n))
{
memset(v,0,sizeof(v));
memset(B,0,sizeof(B));
for(int i=0;i<n;i++)
{
scanf("%I64d",A+i);
ll tp=A[i];
for(ll k=2;k*k<=tp;++k)
if(tp%k==0)
{
v[k]=1;
while(tp%k==0)
{
++B[i][k];
tp/=k;
}
}
if(tp>1){v[tp]=1;B[i][tp]=1;}
}
ll res=1;
for(int i=2;i<9998;i++)
if(v[i])
{
ll t=sol(i);
if(!~t){res=-1;break;}
res=res*Pow((ll)i,t)%M;
}
printf("%I64d\n",res);
}
}

1. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥