1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
using namespace std; typedef long long ll; const int N = 50000 + 10;
int mu[N], vis[N], p[N], tot;
ll (int n, int m, int d) { ll ans = 0; if(n > m) swap(n, m); n /= d, m /= d; for(int i = 1, j ; i <= n ; i = j + 1) { j = min(n / (n / i), m / (m / i)); ans += (ll) (mu[j] - mu[i - 1]) * (n / i) * (m / i); } return ans; }
void () { int a, b, c, d, k; scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); ll ans = sol(b, d, k) + sol(a - 1, c - 1, k) - sol(a - 1, d, k) - sol(b, c - 1, k); printf("%lldn", ans); }
int main() { mu[1] = 1; for(int i = 2 ; i <= 50000 ; ++ i) { if(!vis[i]) mu[i] = -1, p[++ tot] = i; for(int j = 1 ; j <= tot && (ll) i * p[j] <= 50000 ; ++ j) { vis[i * p[j]] = 1; if(i % p[j] == 0) break; mu[i * p[j]] = -mu[i]; } mu[i] += mu[i - 1]; } int T; scanf("%d", &T); while(T --) sol(); }
|
近期评论