25暑期1

Problem E

\(T\) 组询问，给两个数 \(a,b\)，询问 \(|a^2-b^2|\) 的值在集合 \(C\) 中为第几小，\(C=\{|x^2-y^2|\mid x,y\in N^*,x\not=y\}\)。例如 \(3,5,7,8,9\in C\)，且为前五小。

\(1≤T≤10^4,1≤a,b≤10^9,a\not=b\)。

点击查看题解

设 \(a>b\)。\(a^2-b^2=(a+b)(a-b)\)。则 \(a+b\) 和 \(a-b\) 同奇偶。可推出 \(a^2-b^2\bmod 4 \not=2\)。

又 \(\forall\text{ }m_1\ge 1,\exists\text{ }x_1,y_1\in N^*\)，满足 \(x_1-y_1=m_1\)； \(\forall\text{ }m_2\ge 3,\exists\text{ }x_2,y_2\in N^*\)，满足 \(x_2+y_2=m_2\)。

则 \(C=\{n\mid n\ge3,n\not=4,n\bmod4\not=2\}\)。据此可计算排名。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T, a, b;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        a = abs(a * a - b * b);
        if (a == 3)
            cout << 1 << endl;
        else if (a % 4 == 0)
            cout << (a / 4 - 1) * 3 + 1 << endl;
        else if (a % 4 == 1)
            cout << (a / 4 - 1) * 3 + 2 << endl;
        else if (a % 4 == 3)
            cout << (a / 4 - 1) * 3 + 3 << endl;
    }
    return 0;
}