题解：P9031 [COCI2022-2023#1] Iksevi

先考虑如何判断 (x,y) 是否在直径为 2r 的地毯的角上。

不难发现一个必要条件是 r \mid x \land r \mid y，即 r \mid \gcd(x, y)。

满足这个条件的 (x, y) 在图上是这些：

然后猜出充分条件是 2r \nmid x+y。重申一遍：

• r \mid \gcd(x, y)
• 2r \nmid x+y

考察第二个条件。可以改写成：

于是可以对 x+y 的奇偶性分类讨论。

于是需要预处理 1 \sim 10^7 的约数个数。

// Problem: 
//     P9031 [COCI2022-2023#1] Iksevi
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9031
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define tests
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int D[N];

void solve() {
    int x, y;
    cin >> x >> y;
    if ((x + y) % 2) cout << D[__gcd(x, y)] << '\n';
    else cout << D[__gcd(x, y)] - D[__gcd(__gcd(x, y), x + y >> 1)] << '\n';
}

signed main() {
    for (int i = 1; i < N; ++ i )
        for (int j = i; j < N; j += i) D[j] ++ ;

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
#ifdef tests
    cin >> T;
#endif
    while (T -- ) solve();
    return 0;
}