题解说明

问题描述：
给定多个查询，每次输入两个整数 $x$ 和 $y$。需要根据特定规则计算一个值：

• 如果 $x = y$，答案为 $0$
• 否则设 $z = y - x$，提取 $z$ 中的 $2$ 的因子，记为 $tmp$
• 如果 $x$ 不能被 $tmp$ 整除，答案为 $0$
• 否则答案为 $\text{gcd}(z, \tfrac{x}{tmp})$ 的约数个数

因此问题的核心是：快速求任意数的约数个数，并在查询时高效计算 $\gcd$。

核心思路：
$1.$ 预处理约数个数：

• 使用线性筛法（Euler 筛）预处理 $1 \sim N$ 的约数个数 $d[i]$。
• 对于质数 $i$，$d[i] = 2$。
• 对于合数 $i \times pri[j]$，若 $i$ 与 $pri[j]$ 互质，则 $d[i \times pri[j]] = d[i] \times 2$；
  若 $pri[j]$ 是 $i$ 的质因子，则需修正：
  $d[i \times pri[j]] = d[i] - d[i/pri[j]]$。

$2.$ 查询处理：

• 输入 $x,y$，若相等直接返回 $0$。
• 保证 $x < y$，计算 $z = y - x$。
• 将 $z$ 中的 $2$ 因子全部提取出来，记录 $tmp = 2^k$。
• 若 $x \bmod tmp \neq 0$，返回 $0$。
• 否则计算 $g = \gcd(z, x/tmp)$，答案为 $d[g]$。

$3.$ 输出：

• 每个查询独立处理，输出对应答案。

算法流程：
$1.$ 调用 $init()$，用线性筛预处理 $d[i]$。
$2.$ 输入查询次数 $n$。
$3.$ 对每个查询：

• 读入 $x,y$
• 按规则计算答案
• 输出结果

复杂度分析：

• 预处理：$O(N)$ 时间，$N = 10^7$，线性筛可行。
• 每次查询：
  • $\gcd$ 计算 $O(\log \min(x,y))$
  • 常数操作
• 总复杂度：$O(N + q \log A)$，其中 $q$ 为查询数，$A$ 为输入数值范围。

实现细节与注意点：

• $d[1] = 1$ 特殊处理。
• 线性筛时，注意合数的约数个数计算需要区分是否含有相同质因子。
• $\gcd$ 使用内置函数 $\_\_gcd$。
• 输入输出使用 fast IO，避免超时。

总结：
该代码通过“线性筛预处理约数个数 $+$ $\gcd$ 结合因子分解”的方式，实现了对每个查询 $O(\log n)$

#include <bits/stdc++.h>
using namespace std;

// 定义最大范围，根据题目需求设置
#define N 10000005

// 快速读入函数，提高输入效率
int read() {
    int w = 0, f = 1;
    char c = ' ';

    // 处理正负号
    while (c < '0' || c > '9')
        c = getchar(), f = c == '-' ? -1 : f;

    // 读取数字部分
    while (c >= '0' && c <= '9')
        w = w * 10 + c - 48, c = getchar();

    return w * f;
}

// 全局变量
int pri[N / 10];  // 存储质数
int vis[N];       // 标记非质数，同时存储最小质因子
int d[N];         // 存储每个数的约数个数
int cnt;          // 质数计数器

// 处理单个查询
int solve() {
    int x = read(), y = read();

    // 若两数相等，直接返回0
    if (x == y)
        return 0;

    // 保证x < y
    if (x > y)
        swap(x, y);

    int z = y - x, tmp = 1;

    // 提取z中所有的因子2，tmp记录2的幂次
    while (!(z & 1))
        z >>= 1, tmp <<= 1;

    // 若x不能被tmp整除，返回0
    if (x % tmp)
        return 0;

    // 计算gcd并返回其约数个数
    return d[__gcd(z, x / tmp)];
}

// 初始化函数：预处理约数个数
void init() {
    d[1] = 1;  // 1的约数只有1个

    // 线性筛法预处理
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {  // i是质数
            pri[++cnt] = i;
            d[i] = 2;  // 质数有2个约数（1和自身）
        }

        // 遍历已找到的质数，更新倍数的信息
        for (int j = 1; j <= cnt && i * pri[j] < N; j++) {
            vis[i * pri[j]] = pri[j];  // 标记非质数，记录最小质因子
            d[i * pri[j]] = d[i] << 1;  // 初始约数个数翻倍（假设互质）

            if (!(i % pri[j])) {  // 若pri[j]是i的质因子
                // 修正约数个数计算
                d[i * pri[j]] -= d[i / pri[j]];
                break;  // 保证每个数只被最小质因子筛一次
            }
        }
    }
}

// 主函数
signed main() {
    init();  // 预处理约数个数
    int n = read();  // 读取查询次数

    // 处理每个查询并输出结果
    while (n--)
        printf("%d\n", solve());

    return 0;
}