CF1925B 题解

题目链接

Codeforces

Luogu

题目大意

有一个长度为 \(n\) 且和为 \(x\) 的正整数序列，询问该序列可能的最大公因数。

多测。

简要思路

首先先给出结论：

最终的答案一定是 \(x\) 的因数。

接下来我通过两种方法证明：

一、类似于“更相减损法”

一个序列的 \(\gcd\) 等于该序列前缀和后的 \(\gcd\)。

即我们设该序列为 \(a_1,a_2,a_3,\ldots,a_n\)。

\(\gcd(a_1,a_2,a_3,\ldots,a_n) = \gcd(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,a_1+a_2+a_3+\ldots+a_n) = \gcd(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,x)\)

因为 \(\gcd\) 中含有 \(x\)，且是最大公因数，因此最终答案一定是 \(x\) 的因数。

考虑证明 一个序列的 gcd 等于该序列前缀和后的 gcd 的正确性：

即证明 \(\gcd(A,B) = \gcd(A,A+B)\)。

我们用类似于“更相减损法”来证明。

我们设 \(A,B\) 的最大公约数为 \(g\)，那么 \(A=ag,B=bg\)（其中 \(a,b\) 均为正整数）。

设 \(C=A+B\)，则有 \(C=A+B=ag+bg=(a+b)g\)。

由于 \(a,b > 0\)，所以 $a + b > 0 $，所以 \(A,B,C\) 三者的最大公因数为 \(g\)。

所以我们就证得结论：\(\gcd(A,B,C)=\gcd(A,C)=\gcd(A,A+B)=\gcd(A,B)\)

二、通过子序列来表示 \(x\)

我们设该序列为 \(a_1,a_2,a_3,\ldots,a_n\)，该序列的最大公因数为 \(g\)，则有 \(a_1=b_1\times g,a_2=b_2\times g,a_3=b_3\times g,\ldots,a_n=b_n\times g\)（其中 \(b\) 数组均为正整数）。

因为 \(x\) 为该序列的和，所以 \(x=a_1+a_2+a_3+\ldots+a_n=b_1\times g+b_2\times g+b_3\times g+\ldots+b_n\times g=(b_1+b_2+b_3+\ldots+b_n)\times g\)。

所以 \(g\) 一定是 \(x\) 的因子。

用人话来解释一下，就是通过 \(a\) 数组的值的乘法分配律得到 \(x\) 的值，然后 \(x\) 的值是由一个大于等于 \(n\) 的正整数 \(\times g\) 组成的，因此 \(g\) 一定是 \(x\) 的因子。

以上就是两种证明方法。

知道了答案一定是 \(x\) 的因子后，我们再来考虑什么样的因子可以作为答案。

现在我们考虑 \(x\) 的一个因子 \(d\)，如果 \(n \times d \leq x\)，则我们可以选择该序列为 \(d,d,d,\ldots,x-(n-1)\times d\)，因为 \(d\) 为 \(x\) 的因子且 \(n \times d \leq x\)，所以最后一个数 \(x-(n-1)\times d\) 还可以表示为 $(x / d-n-1)\times d $。

所以该序列的每个数都为 \(d\) 的倍数，因此 \(d\) 可能成为答案。

但如果当前的因子 \(d\) 使得 \(n\times d > x\)，即 \(x/d<n\)，那么我们就无法用 \(d\) 这个因子填满整个序列，因此无法对答案影响。

因此我们只需枚举 \(x\) 的因数并判断其是否满足 \(\times n \le x\) 即可。

但是要注意，\(1\leq x\leq 10^8\)，所以我们不能直接枚举 \(1\) 到 \(x\)，需要使用和判断质数中一样的思想——平凡因子分解的方法（即枚举到根号）来解决。

复杂度 \(O(T\sqrt x)\)。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

int T,x,n;

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin>>T;
	while(T--){
		std::cin>>x>>n;
		int maxn=-1;
		
		for(int i=1;i*i<=x;i++){//平凡因子分解
		    if(x%i==0){
		    	if(i*n<=x)maxn=std::max(maxn,i);
		    	if(x/i*n<=x)maxn=std::max(maxn,x/i);
			}
		}
		std::cout<<maxn<<endl;
	}

	return 0;
}

THE END.

THANK YOU.