脚本宝典收集整理的这篇文章主要介绍了SP18202 HG - HUGE GCD 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
目前90ms没开O2（也不知道能不能开O2） 感觉自己的思路挺简单的 题目传送门
题目大意是求 (N) 和 (M) 的最大公因数，所以考虑将 (N) 和 (M) 质因数分解求出每个质因子，由于 (N) 和 (M) 都是很大很大的数字，所以采取对 (N) 和 (M) 的因子进行质因数分解。 以 (N) 为例子
for(k=1;k<=n;k++)
{
scanf("%lld",&t);
if(t<=1)
continue;
for(i=2;i*i<=t;i++)
while(t%i==0)
a[++la]=i,t/=i;
if(t>1)
a[++la]=t;
}
这里我采取了最朴素的质因数分解法，进行暴力枚举。 在对 (M) 也进行质因数分解后，不禁引发了思考：如何找出 (N) 和 (M) 的公共质因子，也就是两个数组中相同的元素呢？这里显然不能像明明的随机数一样进行桶排序。 我采取了Freedom_King太懒没写的方法，排序之后双指针合并。
pa=pb=1;
for(;;)
{
if(pa>la||pb>lb)
break;
if(a[pa]<b[pb])
pa++;
else if(a[pa]>b[pb])
pb++;
else
{
c[++lc]=a[pa];
pa++;
pb++;
}
}
先对数组进行排序，这样保证数组是递增的，两个指针分别指向 (A_i) 和 (B_i) 表示当前质因子大小。
显然如果 (A_i) 小于 (B_i) 时必须把 (P_a) 右移才能保证枚举到相同的质因子， (A_i) 大于 (B_i) 时必须把 (P_b) 右移才能保证枚举到相同的质因子，两者正好相等就能提取出相同的质因子然后指针一起右移，这样就可以快速不遗漏找出所有的质因子存放在数组 (C) 里。
最后要求输出最大公因数的后九位，要求保留前导零。
不妨设立一个变量来判断 (ans) 是否超过 (10^9) ，如果某次超过了就截取后九位并且偷偷记下来，在输出时输出前导零。
我一交，很快啊，240ms，但是我觉得仍然可以进行优化。
最可以优化的就是质因数的判断，考虑到 (10^9 leq 40000) ,可以把 (40000) 以内的质数线性筛出来，在枚举时直接枚举质数，就这样卡到了90ms！
你们最喜欢的源代码。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define int long long
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
int a[100007],b[100007],c[100007],la,lb,lc,pa,pb;
int pt[40007],len;
bool pr[40007];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int i,j,k;
int n,m,t;
for(i=2;i<=40000;i++)
{
if(!pr[i])
pt[++len]=i;
for(j=1;j<=len&&i*pt[j]<=40000;j++)
{
pr[i*pt[j]]=1;
if(!(i%pt[j]))
break;
}
}
scanf("%lld",&n);
for(k=1;k<=n;k++)
{
scanf("%lld",&t);
if(t<=1)
continue;
for(i=1;pt[i]*pt[i]<=t;i++)
while(t%pt[i]==0)
a[++la]=pt[i],t/=pt[i];
if(t>1)
a[++la]=t;
}
sort(a+1,a+1+la);
scanf("%lld",&m);
for(k=1;k<=m;k++)
{
scanf("%lld",&t);
if(t<=1)
continue;
for(i=1;pt[i]*pt[i]<=t;i++)
while(t%pt[i]==0)
b[++lb]=pt[i],t/=pt[i];
if(t>1)
b[++lb]=t;
}
sort(b+1,b+1+lb);
pa=pb=1;
for(;;)
{
if(pa>la||pb>lb)
break;
if(a[pa]<b[pb])
pa++;
else if(a[pa]>b[pb])
pb++;
else
{
c[++lc]=a[pa];
pa++;
pb++;
}
}
int ans=1;
bool flag=1;
for(i=1;i<=lc;i++)
{
ans*=c[i];
if(ans>1000000000)
{
ans%=1000000000;
flag=0;
}
}
if(flag)printf("%lldn",ans);
else printf("%09lldn",ans);
return 0;
}
不准跟我说卡常数快读什么的
以上是脚本宝典为你收集整理的SP18202 HG - HUGE GCD 题解全部内容，希望文章能够帮你解决SP18202 HG - HUGE GCD 题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。