题解 SP18202 【HG - HUGE GCD】

· · 题解

题目大意

给定长度分别为 n,m 的序列 A,B，计算：

\gcd\left(\prod_{i=1}^nA_i,\prod_{j=1}^mB_i\right)

如果答案大于 9 位，输出最后 9 位。1\le n,m\le 10^3;1\le A_i,B_i\le 10^9。

题解

其实这题并不需要对于每个数分解质因数呢。

从简单的地方开始考虑。计算出 A_1 里面的因子会对答案构成的贡献。那么我们可以依次枚举 B_1,B_2,\cdots B_m，然后分别计算 \gcd(A_1,B_i)。每计算一个 d=\gcd(A_1,B_i)，就让 A_1 和 B_i 除去 d，并让答案乘上 d。这么做可以计算出 A_1 的因子对于两方 \gcd 的影响。处理完 A_1，接着处理 A_2,A_3,\cdots A_n。最终得到的答案其实就是题目所求。

要注意的是这题输出格式的小坑。如果算出来的结果会超过九位数，取最后九位时必须要加上前导零。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN =1e3+3;
const i64 MOD  =1e9;
int n,m,A[MAXN],B[MAXN]; i64 ans=1; bool f;
int gcd(int a,int b){return a?gcd(b%a,a):b;}
int main(){
    n=qread(); up(1,n,i) A[i]=qread();
    m=qread(); up(1,m,i) B[i]=qread();
    up(1,n,i) up(1,m,j){
        int d=gcd(A[i],B[j]); A[i]/=d,B[j]/=d;
        if((ans=ans*d)>=MOD) f=true; ans%=MOD;
    }
    if(f) printf("%09lld\n",ans); else printf("%lld\n",ans);
    return 0;
}