CF1925B 题解

CheZiHe929 · 2024-01-29 22:14:01 · 题解

CF1925B 题解

本文同步发于 博客园。

题目链接

Codeforces

Luogu

题目大意

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

多测。

简要思路

首先先给出结论：

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

接下来我通过两种方法证明（为啥其他题解都不证啊）：

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

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

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

因为 \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.