题目

https://www.luogu.com.cn/problem/P12345

思路

对于没有明确给出搜索范围的“计数”或“求解”问题，直接进行暴力枚举几乎总是错误的，除非能从数学上证明所有解都必然在一个有限且可控的范围内。

需要进行数学转换，直接不动脑子进行枚举一定是不能得到正确答案的。

数学推导过程

第一步：建立数学模型

根据题目描述，我们需要找到一个正整数 $n$，使得 $n+20255202$ 和 $n+10244201$ 均为完全平方数。
设这两个完全平方数分别为 $a^2$ 和 $b^2$（其中 $a, b$ 为正整数），从而问题转化为：求解 $n$ 的个数，$n$ 满足以下方程组：

$$ \begin{cases} n + 20255202 = a^2 \\ n + 10244201 = b^2 \end{cases} $$

由于 $n$ 是正整数，可以推断出 $a^2 > 20255202$ 且 $b^2 > 10244201$。同时，显然有 $a^2 > b^2$，即 $a > b$。

第二步：消元与变换

为了找出 $a$ 和 $b$ 之间的关系，我们将方程组中的两个式子相减，以消去变量 $n$：

$$ (n + 20255202) - (n + 10244201) = a^2 - b^2 $$

简化后得到：

$$ a^2 - b^2 = 10011001 $$

这一步是解题的核心突破口，它将问题与变量 $n$ 解耦，转向研究 $a$ 和 $b$ 的性质。

第三步：应用平方差公式

我们对上一步得到的等式左边应用平方差公式：

$$ (a - b)(a + b) = 10011001 $$

这个变换将问题从寻找两个平方数，转化为了对整数 10011001 进行因数分解。

第四步：引入因子并分析

为了方便表示，我们令 10011001 的一对因子为 $d$ 和 $D$，即：

• $d = a - b$
• $D = a + b$

则原方程变为：

$$ d \cdot D = 10011001 $$

根据 $a > b > 0$ 的事实，我们可以确定因子 $d$ 和 $D$ 的性质：
1. $D = a+b > a-b = d$，所以 $D$ 是较大的因子。
2. $d = a-b > 0$，所以 $d$ 和 $D$ 都是正整数。

第五步：求解与回代

现在我们有了一个关于 $a$ 和 $b$ 的新方程组：

$$ \begin{cases} a + b = D \\ a - b = d \end{cases} $$

联立求解这个方程组，可以得到 $a$ 和 $b$ 的表达式：

$$ a = \frac{D+d}{2} $$

$$ b = \frac{D-d}{2} $$

总结：
问题的本质：我们只需要找到 10011001 有多少对不同的因子 (d, D)，然后根据这对因子求出一对a,b，每一对a,b都对应着一个n。

其中，a > sqrt(20255202)和b > sqrt(10244201)是等价的，都满足n>0，只需判断其一即可。

Code

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

int main()
{
    int res = 0;
    int n = 10011001;
    for(int i = 1; i <= n/i; i ++)
    {
        if(n % i == 0)
        {
            if(n / i != i) //满足D>d条件
            {
                int d = i, D = n/d;
                int a = (D+d) / 2;//根据关系计算出a

                if(a > sqrt(20255202))//满足范围条件
                    res ++;             
            }
        }
    }
    printf("%d",res);
    return 0;
}