洛谷10月月赛 II & X Round 4 Div.1 【XR-4】题

数学推式子

先膜拜一下考场上直接切掉的燃情巨佬。

首先分析一下部分分。（蒟蒻并没有分析出\(b=0\)的解法）

对于\(a=b\)的情况，只要满足\(x=y\)即可，所以一共有\(inf\)组解。

对于\(a\le 1000\)的情况，我们直接暴力判断一下即可。

对于\(a=0\)的情况，我们需要求\(y^2 - x^2=b\),就是\((y-x)\times(y+x)=b\),发现这两项都是\(b\)的约数，所以我们\(\sqrt n\)枚举一下\(b\)的约数，若是要有正整数解，就需要\(b- \frac{b}{i}\)是偶数（想一想，为什么）,累加一下答案即可。

void slove1()
{
    for(int i=1;i*i<=b;++i)
    {
        if(!(b%i))
        {
            if(!((b/i-i)&1))++ans;
        }
    }
    cout<<ans;
}

考场亲测综合使用可获得60+的分数。

满分做法

我们可以通过打表发现答案都非常小，\(y-x\)也很小，所以我们可以放弃枚举x，枚举一下\(y\)比\(x\)大多少。我们设为\(g\),即\(y=x+g\),原式也就变为

\((x+g)^2-x^2=ax+b\)

将左边化简一下可得

\(g^2 + 2gx = ax+b\)

将与\(x\)有关的移到一边。

\(g^2-b=(2g-a)x\)

再移动一下

\(x=\frac{g^2-b}{2g-a}\)

又因为我们确定了\(x\)后就可以确定\(y\),\(x\)和\(y\)都是自然数，\(g^2-b\)单调递增，\(2g-a\)单调递减，所以我们能确定一个\(x\)为自然数的最大边界。

n = max((int)sqrt(b) + 1, a / 2 + 1);
for (int g = 0; g <= n; ++g) 
{
    if (a == 2 * g)continue;
    if (!((g * g - b) % (a - 2 * g)) && ((g * g - b) / (a - 2 * g) >= 0))++ans;
}

我们只在这个边界里枚举就行了，最大不会超过1e7。

再说一下inf的情况

由打表可得\(b=(\frac{a}{2})^2\)(a为偶数)时无解。

我们能将式子等价的化为\(4b-a^2=(2y-2x-a)\times(2y+2x+a)\),倘若\(b=(\frac{a}{2})^2\)，那么式子左边就等于0，\((2y+2x+a)\)恒大于0，而\((2y-2x-a)=0\)又有无数种解，所以这时判一下inf即可。

代码其实还是很短的

#include <bits/stdc++.h>
#define LL long long
using  namespace std;
LL a, b, ans, n, f;
signed main() 
{
    cin >> a >> b;
    if (!a && !b)puts("inf");
    else if ((!(a & 1)) && a * a / 4 == b)puts("inf");
    else 
    {
        n = max((LL)sqrt(b) + 1, a / 2 + 1);
        for (LL g = 0; g <= n; ++g) 
        {
            if (a == 2 * g)continue;
            if (!((g * g - b) % (a - 2 * g)) && ((g * g - b) / (a - 2 * g) >= 0))++ans;
        }
        cout << ans;
    }
}