CSP-J 2023 第一轮 第 31 题：程序（三）：两个输出值的差值范围

题目

#include <iostream>
#include <cmath>
using namespace std;

int solve1(int n){
    return n*n;
}

int solve2(int n){
   int sum=0;
   for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            if(n/i==i){
                sum+=i*i;
            }else{
                sum+=i*i+(n/i)*(n/i);
            }
        }
    }
    return sum;
}
int main(){
    int n;
    cin>>n;
    cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
    return 0;
}

假设输入的 $n$ 是绝对值不超过 $1000$ 的整数，完成下面的判断题和单选题。

当输入为正整数时，第一项减去第二项的差值一定（ ）

选项

• A. 大于 $0$
• B. 大于等于 $0$ 且不一定大于 $0$
• C. 小于 $0$
• D. 小于等于 $0$ 且不一定小于 $0$

答案

D

题解

选 D：小于等于 \(0\)，且不一定小于 \(0\)（按题目意图，不考虑整数溢出）。

solve1(n) 返回 \(n^2\)。solve2(n) 枚举成对的因数，并避免重复计算平方根，因此返回 \(n\) 的所有正因数的平方和。记为 \[ S(n)=\sum_{d\mid n}d^2. \] 那么两个输出分别是 \(S(n^2)\) 和 \(S(n)^2\)。

关键是比较： \[ S(n)^2 =\left(\sum_{a\mid n}a^2\right)\left(\sum_{b\mid n}b^2\right) =\sum_{a\mid n,\ b\mid n}(ab)^2. \]

这里有两个性质：

• \(a,b\) 都是 \(n\) 的因数，所以 \(ab\) 是 \(n^2\) 的因数。
• \(n^2\) 的每个因数，都能写成两个 \(n\) 的因数的乘积。因为若某个质因子在 \(n\) 中的指数为 \(k\)，它在 \(n^2\) 的因数中的指数至多为 \(2k\)，总能拆成两个不超过 \(k\) 的指数。

因此，右边包含了 \(S(n^2)\) 的所有项，而且可能重复计算，故 \[ S(n)^2\ge S(n^2), \qquad \boxed{S(n^2)-S(n)^2\le0}. \]

再看是否能取等号：

• \(n=1\)：两个输出都是 \(1\)，差为 \(0\)。
• \(n>1\)：\((a,b)=(1,n)\) 和 \((n,1)\) 会重复贡献 \(n^2\)，所以差严格小于 \(0\)。

所以选 D。

补充：原代码使用 int，在题目给出的范围内确实可能溢出；例如 \(n=1000\) 时会计算 \(10^{12}\)。实际实现应使用 long long。