平方差-蓝桥杯

平方差

题目描述

题解

由平方差公式：\(y^2-z^2=(y+z)(y-z)\)，不妨设\(x=ab\)，令$$y+z=a$$ $$y-z=b$$则只要 \(a,b\) 奇偶性相同，\(y,z\) 就有整数解。若 \(x\) 为奇数，则 \(x\) 可以分解为1和 \(x\) ，若 \(x\) 为偶数，则只有当 \(x\) 为4的倍数时，可以被分解为2和 \(\frac{x}{2}\) （这是因为若要满足 \(x\) 为偶数且 \(a,b\) 奇偶性相同，则 \(x\) 必然为偶数个偶数相加得到的，则与4的倍数等价）才能满足条件。
根据该分析，我们可以写出如下代码:

#include<iostream>
#include<vector>
using namespace std;
int l, r, ans = 0;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> l >> r;
    for(int i = l; i <= r; i++)
    {
        if(i & 1)
        {
            ans++;
        }
        else if(i % 4 == 0)
        {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

然而由于数据范围最大为 \(10^9\) ，因此会有部分数据超时。我们做出改进，可以在 \(O(1)\) 的时间里找到 \(L,R\) 中2的倍数和4的倍数。我们将 \(L,R\) 中的总数减去2的倍数，剩下的即为奇数的个数，再加上4的倍数，最后就是所求的答案。

#include<iostream>
#include<vector>
using namespace std;
int l, r, ans = 0;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> l >> r;
    int total = r - l + 1;
    int multiple_2 = r / 2 - (l - 1) / 2;
    int multiple_4 = r / 4 - (l - 1) / 4;
    ans = total - multiple_2 + multiple_4;
    cout << ans;
    return 0;
}

注：\([0,n]\) 中 \(x\) 的倍数的个数为 \(int(\frac{n}{x})\) ，这是因为乘法本质上就是加法。