P2522 [HAOI2011]Problem b

P2522 [HAOI2011]Problem b

与 P3455 类似，
只不过 变成了 。

两种方法解决：

用前缀和，转化为 四个 。

整除分块的时候分为四条轴。要注意的是其中两条 轴很快会变为0，此时就不能用 来更新 了。 否则分母会为

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i ++)
#define dwn(i,a,b) for(int i = (a); i >= (b); i --)
using namespace std;
const int maxn = 50000 + 1000;

ll mu[maxn];
int cur, p[maxn], isp[maxn];
void shai()
{
    int n = 50000;
    mu[1] = 1;
    rep(i, 2, n)
    {
        if(!isp[i])
        {
            p[ ++ cur] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cur && i * p[j] <= n; j ++)
        {
            isp[i * p[j]] = 1;
            if(i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            else
            {
                mu[i * p[j]] = mu[i] * mu[p[j]];
            }
        }
    }
    rep(i, 2, n)
        mu[i] = mu[i - 1] + mu[i];
}
int main()
{
    shai();
    int T;
    cin >> T;
    rep(i,1, T)
    {
        ll Ans = 0;
        ll a, b, c, d, k;
        scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &k);
        int N = min(b, d) / k;
        ll l1, r1, l2, r2;
        r1 = b / k;
        l1 = (a - 1) / k;
        r2 = d / k;
        l2 = (c - 1) / k;
        for(ll l = 1, r;l <= N; l = r + 1)
        {
            r = min(r1 / (r1 / l), r2 / (r2 / l));
            if(l <= l1)
                r = min(r, l1 / (l1 / l));
            if(l <= l2)
                r = min(r, l2 / (l2 / l));
            Ans += (mu[r] - mu[l - 1]) * (r1 / l - l1 / l) * (r2 / l - l2 / l);
        }
        printf("%lld\n", Ans);
    }
    return 0;
}