思路与算法

正整数x的数根k满足x≡k(mod9)，k=1..9。因此喜欢数y=kx恰落入y≡k²(mod9k)的正数等差数列。9个周期的公倍数为22680，预先对一个周期标出并集，做前缀计数。F(R)=整周期数×周期喜欢数+余段计数，答案F(R)-F(L-1)。

正确性说明

数根的模9刻画是充要条件，故九条数列的并集恰是全部喜欢数，同一数即使由多个k生成也只标一次。22680能被每个9k整除，因此并集指示函数按此周期重复，按整段与余段拆分计数准确。

复杂度

预处理O(22680+Σ22680/(9k))时间、O(22680)空间，包含标记清空与前缀和；每组询问O(1)，总O(22680+T)。计数和端点用64位无符号整数。

易错点

x仅正数，周期余数0对应周期末而不是整数0。L=1时F(0)=0。不可把不同k的计数直接相加导致交集重复。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int P = 22680;
    vector<int> hit(P), pref(P + 1);
    for (int k = 1; k <= 9; k++)
        for (int a = k * k; a <= P; a += 9 * k)
            hit[a % P] = 1;
    for (int i = 1; i <= P; i++)
        pref[i] = pref[i - 1] + hit[i % P];
    auto F = [&](unsigned long long x) {
        return x / P * pref[P] + pref[x % P];
    };
    int T;
    cin >> T;
    while (T--) {
        unsigned long long l, r;
        cin >> l >> r;
        cout << F(r) - F(l - 1) << '\n';
    }
}