[bzoj 2301] [HAOI2011]Problem b

求满足a≤x≤b, c≤y≤d, 且gcd(x,y)=k的(x,y)的数目. n个询问. (1≤n,k,c,d≤50000, a≤b, c≤d) 可以这样考虑. gcd(x,y)=k的(x,y)的数目不那么容易求, 但gcd(x,y)是k的倍数的(x,y)的数目是易求的, 它等于, 且. 莫比乌斯反演, 得到, 于是

莫比乌斯函数表可以借助于线性筛来打. 但现在算一次还是很慢......

看到整除, 联想到分段性, 所以单次查询可优化到根号级别.

由于事先知道这是莫比乌斯反演, 所以我是直接从定义开始推的, 把替换成莫比乌斯函数. 试图从反演的角度看问题, 却发现这里是倍数不是约数. 以前不知道, 倍数方向的反演也是成立的. 二项式反演也有类似的结论.

const int N = 5e4, inf = 1e8;
typedef long long ll;
int mu[N + 1], S[N + 1];
 
void sieve()
{
    static int prime[N/2];
    static bool f[N + 1];
    int cnt = 0;
    mu[1] = 1;
    For (i, 2, N) {
        if (!f[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0, t; j < cnt && (t = prime[j]*i) <= N; ++j) {
            f[t] = true;
            if (i % prime[j]) mu[t] = -mu[i];
            else break;
        }
    }
    For (i, 1, N) S[i] = S[i-1] + mu[i];
}
 
ll cal(int a, int b, int c, int d)
{
    ll ans = 0;
    --a, --c;
    for (int i = 1, ed = min(b, d), j; i <= ed; i = j+1) {
        int _a = a/i, _b = b/i, _c = c/i, _d = d/i;
        j = min(ed, min(b/_b, d/_d));
        if (_a) j = min(j, a/_a);
        if (_c) j = min(j, c/_c);
        ans += (ll)(S[j] - S[i-1]) * (_b - _a) * (_d - _c);
    }
    return ans;
}
 
int main()
{
    sieve();
    int n;
    scanf("%d", &n);
    while (n--) {
        int a, b, c, d, k;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        printf("%lld\n", cal((a+k-1)/k, b/k, (c+k-1)/k, d/k));
    }
    return 0;
}