P12828 「DLESS-2」XOR and Number Theory

· · 题解

宝宝题，喜提最劣解。

思路：

首先 y \oplus x = \gcd(x, y) 特别经典，设 y > x，因为 y \oplus x \ge y - x \ge \gcd(x, y)，所以设 d = \gcd(x, y)，那么限制是 y \oplus x = d = y - x。

再来考虑求的是什么，设 x = kd, y = (k + 1)d，于是：

\begin{aligned} LHS &= x^2 \bmod {(y^2 - xy)} \\ &= k^2 d^2 \bmod {((k + 1)^2 d^2 - d^2 k(k + 1))} \\ &= k^2 d^2 \bmod {(d^2 (k + 1))} \\ &= d^2 (k^2 \bmod {(k + 1)}) \\ &= d^2\end{aligned}

注意到 d \le m 是比较小的，所以考虑枚举 d 去算合法的 (x, y) 的对数，显然一个 y 要满足以下两个条件：

设此时 d 的二进制下最高位是 h，那么上面条件相当于 y 的二进制前 h 位是 d 的超集，于是我们再枚举一个 y 的前 h 位 d \subseteq p，然后对于 y 的限制现在本质是在解同余方程组：

\begin{cases} y \equiv 0 \pmod d \\ y \equiv p \pmod {2^{h + 1}}\end{cases}

我们要求这个解 \le n 的数量，可以直接 excrt 解出通解然后就好做了。

时间复杂度为 O(3^{\log m} + m \log m)。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcountll(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 10, mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, m;
int ans;
int lg[N];
inline void exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
}
inline void init(){
    lg[0] = 0;
    for(int d = 1; d < N; ++d)
        lg[d] = lg[d >> 1] + 1;
}
inline void solve(){
    ans = 0;
    n = read(), m = read();
    for(int d = 1; d <= m; ++d){
        ll sum = 0;
        int h = lg[d];
        int all = (1 << h) - 1, p2 = (1 << h);
        int dd = __gcd(d, p2);
        int _d = d / dd, _p2 = p2 / dd;
        int x, y;
        exgcd(_d, _p2, x, y);
        if(x < 0)
          x += _p2;
        ll Y = 1ll * d * _p2;
        // if(Y > n)
        //   continue;
        // cerr << d << ' ' << h << ' ' << p2 << '\n';
        for(int p = d; p <= all; p = (p + 1) | d){
            // y \equiv 0 mod d
            // y \equiv p mod p2
            // kd \equiv p mod p2
            // dd = __gcd(d, p2)
            // p % dd != 0 -> no ans
            // k *(d / dd) \equiv (p / dd) mod {p2 / dd}
            // k = \equiv (p / dd) * (d / dd)^{-1} {p2 / dd}
            // k -> kk (p2 / dd) + X
            // y = kd -> kk * d * (p2 / dd) + X * d
            // Y = d * (p2 / dd)
            // cerr << dd << ' ' << p << '\n';
            if(p % dd != 0)
              continue;
            // cerr << x << ' ' << y << '\n';
            ll X = (1ll * (p / dd) * x % _p2) * d;
            // cerr << X << ' ' << Y << '\n';
            // y = kk * Y + X <= n
            // kk * Y <= n - X
            // 0 <= kk <= (n - X) / Y
            if(X > n)
              continue;
            if(Y > n)
              ++sum;
            else
              sum += (n - X) / Y + 1;
        }
        --sum;
        ans = (ans + sum % mod * d % mod * d % mod) % mod;
    }
    write(ans);
    putchar('\n');
}
int main(){
    init();
    T = read();
    while(T--)
      solve();
    return 0;
}