SP18202 HG - HUGE GCD 题解
题意：
求
保留 $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
