# SP18202 HG – HUGE GCD 题解(Sp18202 HG – huge GCD solution)-其他

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

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


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


#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!

#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