最大公约数
没想到被这么水的题卡了
给定n，以及正整数序列a1,a2,…,an与b1,b2,…,bn。
令：
sa=a1*a2*…*an
sb=b1*b2*…*bn
求sa和sb的最大公约数gcd(sa,sb)。
10<=n<=100 1<=ai,bi<=10000
sa,sb<=10^400
#include<bits/stdc++.h>using namespace std;
long long n,a[101],b[101],ans=1;
long long gcd(long long a,long long b)
{ long long c;
while(b)
{
c=a%b;
a=b;b=c;
}
return a;
}int main()
{ cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
long long jii=gcd(a[i],b[j]);
a[i]/=jii;b[j]/=jii;
ans*=jii;
ans%=10007;//比赛时写了ans%100000，就...... if(a[i]==1)
break;
}
}
cout<<ans%10007;
}赛后想明白了，ans%10007剩下来的都是答案相关的
但%100000完了可能与答案不一样，不能整除