自动搬运

查看原文

来自洛谷，原作者为

	oyoham ~RESSURRECTED~

搬运于2025-08-24 22:44:07，当前版本为作者最后更新于2024-09-03 09:52:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem

给定长为 $n$ 的数组 $Y$ 和正整数 $m$，要构造长为 $n$ 的数组 $X$ 使得满足：

1. $\forall 1\le i\le n,-2^{127}\le X_i\le 2^{127}-1$。
2. $\forall 1\le i\le n,X_i \bmod m = Y_i$。
   求 $\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$。
证明：
$Y_i$ 只能对 $\gcd$ 产生 $Y_i$（取 $k_i\ge0$）或 $m-Y_i$（取 $k_i<0$）的贡献。
与 $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;
}