SP18202 HG – HUGE GCD 题解(Sp18202 HG – huge GCD solution)

目前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("%lld\n",ans);
	else printf("%09lld\n",ans);

	return 0;
}

不准跟我说卡常数快读什么的

————————

At present, O2 is not turned on for 90ms (I don’t know if O2 can be turned on)
I feel my idea is very simple
Title portal

The main idea of the topic is to find the maximum common factor of \ (n \) and \ (m \), so it is considered to decompose the \ (n \) and \ (m \) prime factors to find each prime factor. Since \ (n \) and \ (m \) are very large numbers, the prime factor solution is adopted for the factors of \ (n \) and \ (m \).
Take \ (n \) as an example

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

Here I take the most simple prime factor decomposition method for violent enumeration.
After the prime factor decomposition of \ (m \), I can’t help thinking: how to find the common prime factors of \ (n \) and \ (m \), that is, the same elements in the two arrays? Obviously, bucket sorting can not be carried out like explicit random numbers.
I took freedom_ King is too lazy to write a method. After sorting, double pointers are merged.

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++;
	}
}

Sort the array first to ensure that the array is incremented. The two pointers point to \ (a_i \) and \ (b_i \) respectively to indicate the current prime factor size.
Obviously, if \ (a_i \) is less than \ (b_i \), you must move \ (p_a \) to the right to ensure enumeration to the same quality factor. If \ (a_i \) is greater than \ (b_i \), you must move \ (p_b \) to the right to ensure enumeration to the same quality factor. If they are exactly equal, you can extract the same quality factor, and then move the pointer to the right together, In this way, we can quickly find all the prime factors without missing them and store them in the array \ (C \).
Finally, it is required to output the last nine bits of the maximum common factor and keep the leading zero.
You might as well set up a variable to judge whether \ (ANS \) exceeds \ (10 ^ 9 \). If it exceeds it once, intercept the last nine bits and secretly write it down, and output the leading zero during output.
I handed it in soon, 240ms, but I think it can still be optimized.
The best thing to optimize is the judgment of the prime factor. Considering \ (10 ^ 9 \ Leq 40000 \), you can linearly screen out the prime numbers within \ (40000 \), and directly enumerate the prime numbers during enumeration. In this way, it is stuck for 90ms!
Your favorite source code.

#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("%lld\n",ans);
	else printf("%09lld\n",ans);

	return 0;
}

Don’t tell me to read fast