SP18202 HG - HUGE GCD 题解

题目链接：SP18202 HG - HUGE GCD

题意：

求 \[ \gcd\left(\prod_{i=1}^N A_i, \prod_{i=1}^M B_i\right) \] 保留 \(9\) 位数字。 \(1\le N,M \le 10^3,1 \le A_i, B_i \le 10^9\) 。

这个题很明显，我们只需要把两侧的数全都质因数分解，

然后扫一遍，每个质因数取两侧最小的值即可。比如左边有 \(2^33^2\) ，右边有 \(2^23^3\) ，那就取 \(2^23^2\) 。

这样做的复杂度应该是 \(\mathcal{O}(n \log^2 n + n \sqrt{M})\) ，其中 \(M\) 为 \(A_i,B_i\) 的值域。

不过这个做法需要对每个数都进行一次质因数分解，cxy 觉得这样很粗鲁，所以我们讲一种不需要分解的做法

我们依次考虑每个 \(A_i\) ，然后枚举 \(B_j\) 。记 \(d = \gcd(A_i, B_j)\) ，然后令 \(A_i,B_j\) 除以 \(d\) ，答案乘上 \(d\) 。

这样做的最坏时间复杂度是 \(\mathcal{O}(n^2\log n)\) ，但是实际上运行的效果还是不错的，并且很优雅。

代码：（来自参考文献[1]）

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

---

补充：

在C/C++的宏定义中，## 是一种称为“连接运算符”的特殊符号。它用于将两个标识符（包括宏参数）连接在一起形成一个新的标识符。

在上面的代码中，## 用于将 "END" 和参数 "i" 连接在一起，生成一个新的标识符。这在宏定义中很有用，因为它允许在每次宏调用时生成一个唯一的标识符。

具体来说，END##i 将会展开为一个新的标识符，其名称是由 "END" 和参数 "i" 连接而成。例如，如果宏调用是 up(1, 5, j)，那么 ## 将会将 "END" 和 "j" 连接成一个新的标识符 "ENDj"。

这样做的目的是为了确保在多次调用宏函数时，每次都会生成一个不同的标识符，避免命名冲突和重复定义的问题。

需要注意的是，## 的使用有一些限制，它只能用于宏定义中，并且只能用于连接标识符。

---

参考文献：

[1] https://www.luogu.com.cn/blog/over-knee-socks/solution-sp18202