自己推导:
直接代入公式:
AC代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 500007, M = 500007,INF = 0x3f3f3f3f;
typedef long long ll;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-')f = -1; ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int a, b, c, d, k;
int mu[N];
int primes[N], cnt;
bool vis[N];
void get_mu(int n)
{
memset(vis, 0, sizeof vis);
memset(mu, 0, sizeof mu);
cnt = 0, mu[1] = 1;
for(int i = 2; i <= n; ++ i)
{
if(vis[i] == 0){
primes[ ++ cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j){
vis[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
mu[i * primes[j]] -= mu[i];
}
}
for(int i = 1; i <= n; ++ i)
mu[i] += mu[i - 1];
}
int solve(int n, int m)
{
n /= k, m /= k;
int res = 0;
for(int i = 1, j; i <= min(n, m); i = j + 1){
j = min(n / (n / i), m / ( m / i));//j是右边界,这里的值都是i
res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
}
return res;
}
int n, m;
int main()
{
get_mu(N - 1);
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
a = read(), b = read(), c = read(), d = read(), k = read();
int ans = solve(b, d) - solve(b, c - 1) - solve(a - 1, d) + solve(a - 1, c - 1);
printf("%d\n", ans);
}
return 0;
}