【题解】最大公约数（2019青岛市程序设计竞赛）
【问题描述】
给定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。
【输入输出样例】
gcd.in | gcd.out |
3 12 15 70 20 75 49 | 2100 |
【数据范围】
测试点 | n范围 | ai,bi,sa,sb |
1 | 1<=n<=5 | 1<=ai,bi<=10000; sa,sb<109 |
2 | ||
3 | ||
4 | 10<=n<=100 | 1<=ai,bi<=10000; sa,sb<10400。 |
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
【来源】
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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。