【问题描述】

给定n，以及正整数序列a1,a2,…,an与b1,b2,…,bn。

令：

sa=a1*a2*…*an

sb=b1*b2*…*bn

求sa和sb的最大公约数gcd(sa,sb)。

【输入】

第一行n。

第二行,序列a1,a2,…,an。两个数之间用空格隔开。

第三行,序列b1,b2,…,bn。两个数之间用空格隔开。

【输出】

sa和sb的最大公约数,结果%10007。

【输入输出样例】

【数据范围】

【来源】

2019年青岛市程序设计竞赛试题（初中组）2T

• 题目的难点在于数据范围和最大公约数的求法。

• 关于最大公约数的求法，可以参见最大公约数求法

• 取余这个操作用公式：（a*b）%p =(a%p * b%p) %p

• 数据范围要用long long

【参考答案】

#include<bits/stdc++.h>
using namespace std;
long long n,sa[101],sb[101],ans=1; 
//求最大公约数 
long long gcd(long a,long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
} 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>sa[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>sb[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            long long devisor=gcd(sa[i],sb[j]); //求最大公约数 
            sa[i]/=devisor;
	    sb[j]/=devisor; //约分 
            ans*=devisor;   //sa与sb的最大公约数等于他们每一项的最大公约数相乘 
            ans%=10007; //取模 
            if(sa[i]==1)
            break;
        }
    }
    cout<<ans%10007;
    return 0; 
}