题解：P8961 「WHOI-4」ggcd
oyoham
·
·
题解
Problem
给定长为 n 的数组 Y 和正整数 m，要构造长为 n 的数组 X 使得满足：
-
-
求 $\gcd\limits_{i=1}^{n}|X_i|\bmod m$ 的最大值，并输出任意对应的数组 $X$。
### Solution
设 $\forall 1\le i\le n,X_i = Y_i + k_i\cdot m$。
先考虑 n=1。
此时答案只可能为 Y_1（取 k_1\ge0）或 m-Y_1（取 k_1<0）。比较并输出即可（可见样例 1,2）。
考虑 k>1。
设 g=\gcd(\gcd\limits_{i=1}^{n}Y_i,m)，可以发现答案为 ans=m-g。
证明：
与 $m$ 取 $\gcd$ 是利用 $\gcd(a,b)=\gcd(a-b,b)$ 将 $\gcd(m-Y_i,Y_i)=\gcd(m,Y_i)$。
考虑构造方法：
先特判掉 $\forall 1\le i\le n,Y_i=0$ 的构造（全输出任意 $m$ 的倍数即可）。
随便找到一个 $p$ 使 $\exist 1\le i\le n \& i\ne p,Y_i\ne0$。对于 $i\ne p$ 时构造 $k_i=-\frac{Y_i}{g}$ 使得 $X_i=-ans\cdot\frac{Y_i}{g}$，满足 $ans|X_i$。
此时设 $G=\gcd\limits_{1\le i\le n,i\ne p}\frac{X_i}{ans}$，考虑使 $k_p=\frac{k'\cdot ans-Y_p}{g}$ 此时有 $X_p=k_p\cdot m+Y_p=\frac{k'\cdot ans \cdot m-Y_p\cdot m + Y_p \cdot g}{g}=\frac{k'\cdot ans \cdot m+Y_p \cdot (g-m)}{g}=\frac{k'\cdot ans \cdot m-Y_p \cdot ans}{g}=ans\cdot\frac{k'\cdot m-Y_p}{g}$ 满足 $ans|X_p$，于是从 $1$ 递增枚举 $k'$（或在范围内随机 $k'$），找到一个 $\gcd(G,\frac{k'\cdot m-Y_p}{g})=1$，即可输出答案了。
### Code
```
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define int ll
#define aF(begin,end,step,name) for(int name=begin;name<=end;name+=step)
#define oF(B,E,N) aF(B,E,1,N)
#define af(B,E,S) aF(B,E,S,i)
#define of(B,E) af(B,E,1)
#define tF(E,N) oF(1,E,N)
#define tf(E) of(1,E)
#define nF(N) tf(n,N)
#define nf() tf(n)
inline ll read(){
ll x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0ll) putchar(45),x=~x+1;
if(x>9ll) write(x/10);
putchar(x%10|48);
}
int n=read(),m=read();
int a[1000005];
int f=1;
int g=m,ans=0;
void Spe(){
int ans=read();
if(ans<<1<m) ans=m-ans,f=-1;
write(ans);putchar(10);write(ans*f);
exit(0);
}
int ABS(int x){
return x>0?x:-x;
}
int ansl[1000005];
int k[1000005];
int tagp=0;
signed main(){
if(n==1) Spe();//特判
nf() a[i]=read();
nf(){
if(a[i]) tagp=i;
g=__gcd(g,a[i]);
}
write((ans=m-g)),putchar(10);
if(!tagp){//是否全0
nf()write(0),putchar(32);
exit(0);
}
int AN=tagp==1?2:1,G=0;//AN为题解中的p，tagp为一个非0点，去一个不为tagp的点即可
nf(){//i!=p部分
if(i==AN)continue;
k[i]=-a[i]/g;
G=__gcd(G,k[i]*m+a[i]);
}
int _k=1;//从1递增写法
k[AN]=(_k*ans-a[AN])/g;
while(__gcd(G,k[AN]*m+a[AN])>ans) _k++,k[AN]=(_k*ans-a[AN])/g;
/*随机写法
int _k=rand();
k[AN]=(_k*ans-a[AN])/g;
while(__gcd(G,k[AN]*m+a[AN])>ans) _k=rand(),k[AN]=(_k*ans-a[AN])/g;
*/
nf(){
write(k[i]*m+a[i]);putchar(32);
}
return 0;
}
```