【问题描述】

给定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;   }

(adsbygoogle = window.adsbygoogle || []).push({});