题目大意
给定两个 square-free number \(A\) 和 \(B\)（即没有一个素因子的次数达到 \(2\) 的数） 的 01 表示形式（即将其有无该素因子排列出来，如 \(105=3\times 5\times 7\)，则 \(105\) 的 01 表示形式为 0111）。求 \(\gcd(A+B,\operatorname{lcm}(A,B))\)。如果结果不是 square-free nunmber 则用十进制输出，如果结果是 \(1\) 则输出 relatively prime。
分析
一道小清新的数论题。
因为 \(A\) 和 \(B\) 是 square-free number，考虑将其唯一分解。设
\[\begin{cases}A=\prod\limits_{i=1}^np_i\\B=\prod\limits_{i=1}^mq_i\\\gcd(A,B)=\prod\limits_{i=1}^cx_i\end{cases} \]将 \(\{p_i\}\) 和 \(\{q_i\}\) 属于 \(\{x_i\}\) 的部分移动到前 \(c\) 个，那么可得：
\[\begin{cases}A+B=\prod\limits_{i=1}^cx_i(\prod\limits_{j=1}^{n-c}p_{j+c}+\prod\limits_{k=1}^{m-c}q_{k+c})\\\operatorname{lcm}(A,B)=\prod\limits_{i=1}^cx_i\prod\limits_{j=1}^{n-c}p_{j+c}\prod_{k=1}^{m-c}q_{k+c}\end{cases} \]容易发现
\[\begin{cases}\forall p_{j+c},\ p_{j+c}\nmid\prod\limits_{j=1}^{n-c}p_{j+c}+\prod\limits_{k=1}^{m-c}q_{k+c}\\\forall q_{k+c}, \ q_{k+c}\nmid\prod\limits_{j=1}^{n-c}p_{j+c}+\prod\limits_{k=1}^{m-c}q_{k+c}\end{cases} \]所以
\[\gcd(A+B,\operatorname{lcm}(A,B))=\gcd(A,B) \]因此直接统计相同素因子即可。答案一定是 square-free number 或 \(1\)。
实现
记得多测清空。
#include<bits/stdc++.h>
#define HohleFeuerwerke using namespace std
#pragma GCC optimize(3,"Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#define int long long
HohleFeuerwerke;
inline int read(){
int s=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) s=s*10+c-'0';
return s*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar('0'+x%10);
}
const int MAXN=2e3+5;
int T,n,m;
char str1[MAXN],str2[MAXN];
bool A[MAXN],B[MAXN],ans[MAXN];
inline void solve(){
memset(ans,0,sizeof(ans));
for(int i=1;i<=max(n,m);i++){
if(A[i]==B[i]&&A[i]==true) ans[i]=true;
else ans[i]=false;
}
int len=0;
for(int i=MAXN-5;i>=1;i--){if(ans[i]==true){len=i;break;}}
if(len==0) puts("relatively prime");
else{
for(int i=1;i<=len;i++) write(ans[i]);
puts("");
}
}
signed main()
{
T=read();
while(T--){
scanf("%s%s",str1+1,str2+1);
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
n=strlen(str1+1),m=strlen(str2+1);
for(int i=1;i<=n;i++){
if(str1[i]=='0') A[i]=false;
else if(str1[i]=='1') A[i]=true;
}
for(int i=1;i<=m;i++){
if(str2[i]=='0') B[i]=false;
else if(str2[i]='1') B[i]=true;
}
solve();
}
return 0;
}