[HAOI 2011]Problem b

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

题解

记 $f(x, y)$ 为满足 $gcd(i,j)=k$ 的数对 $(i,j)~~(iin[1,x],jin[1,y])$ 的个数。

由容斥原理，答案就是 $ans=f(b,d)-f((a-1),d)-f(b,(c-1))+f((a-1),(c-1))$ 。

我们现在考虑如何求 $f(x,y)$ 。

我们按照以往的套路，将 $k$ 提出，显然 $$f(a,b)=sum_{i=1}^{leftlfloorfrac{a}{k} ight floor}sum_{j=1}^{leftlfloorfrac{b}{k} ight floor}[gcd(i,j)=1]$$

由公式 $sum_{dmid n} mu(d)=[n=1]$ ，我们得到

$$Rightarrow sum_{i=1}^{leftlfloorfrac{a}{k} ight floor}sum_{j=1}^{leftlfloorfrac{b}{k} ight floor}sum_{dmid gcd(i,j)}mu(d)$$

我们将 $mu$ 提前

egin{aligned} &Rightarrowsum_{d=1}^{minleft{leftlfloorfrac{a}{k} ight floor,leftlfloorfrac{b}{k} ight floor ight}}mu(d)sum_{i=1,dmid i}^{leftlfloorfrac{a}{k} ight floor}sum_{j=1,dmid j}^{leftlfloorfrac{b}{k} ight floor}1\&Rightarrowsum_{d=1}^{minleft{leftlfloorfrac{a}{k} ight floor,leftlfloorfrac{b}{k} ight floor ight}}mu(d)cdotleftlfloorfrac{leftlfloorfrac{a}{k} ight floor}{d} ight floorcdotleftlfloorfrac{leftlfloorfrac{b}{k} ight floor}{d} ight floorend{aligned}

得到这个式子还有第二个方Fa♂，这里也提一下。

令 $F(d)$ 为 $dmid gcd(i,j)$ 的数对 $(i,j)$ 个数， $f(d)$ 为 $d=gcd(i,j)$ 的数对 $(i,j)$ 个数。

由题 $$F(k)=sum_{d=1}^{minleft{leftlfloorfrac{a}{k} ight floor,leftlfloorfrac{b}{k} ight floor ight}}f(kd)$$

由莫比乌斯反演定理 $F(n)=sum_{nmid d} f(d)Rightarrow f(n)=sum_{nmid d} mu(frac{d}{n})F(d)$

egin{aligned}Rightarrow f(k)&=sum_{d=1}^{minleft{leftlfloorfrac{a}{k} ight floor,leftlfloorfrac{b}{k} ight floor ight}}mu(d)F(kd)\&=sum_{d=1}^{minleft{leftlfloorfrac{a}{k} ight floor,leftlfloorfrac{b}{k} ight floor ight}}mu(d)cdotleftlfloorfrac{a}{kd} ight floorcdotleftlfloorfrac{b}{kd} ight floorend{aligned}

那么我们现在只需要 $O(n)$ 的枚举 $d$ 就可以了，但对于多组询问，这个复杂度还是吃不消的。

我们考虑在计算的时候 $leftlfloorfrac{leftlfloorfrac{n}{k} ight floor}{d} ight floor$ 是一个分段的，有较长的一段区间内的数是相等的。可以证明这段区间的长度是 $sqrt{n}$ 的。

证明：

　　1.当 $1leq d < sqrt n$ 时， $d$ 就只有 $sqrt n$ 个， $leftlfloor{n over d} ight floor$ 最多有 $sqrt n$ 个。

　　2.当 $sqrt n leq d leq n$ 时，由于 $leftlfloor{n over d} ight floor$ 小于 $sqrt n$ ，所以 $leftlfloor{n over d} ight floor$ 最多有 $sqrt n$ 个。

证毕。

显然对于一段区间内 $leftlfloorfrac{leftlfloorfrac{a}{k} ight floor}{d} ight floor$ 和 $leftlfloorfrac{leftlfloorfrac{b}{k} ight floor}{d} ight floor$ 相同的数我们可以直接处理 $mu$ 的前缀，直接求即可。而相同值的区间的右端点为 $leftlfloor frac{n}{leftlfloorfrac{n}{d} ight floor} ight floor$ 。

证明：

对于 $n$ 来说，找到最大的 $j$ 满足 $$leftlfloorfrac{n}{i} ight floor leqleftlfloorfrac{n}{j} ight floor$$

化简一下得到 $$jleq leftlfloorfrac{n}{leftlfloorfrac{n}{i} ight floor} ight floor$$

那么在计算时在分别关于 $a, b$ 的表达式中取一个较小值即可。时间复杂度 $O(nsqrt n)$ 。

//It is made by Awson on 2018.1.19
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('
'))
using namespace std;
const int N = 50000;
const int INF = ~0u>>1;
void read(int &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void write(LL x) {
    if (x > 9) write(x/10);
    putchar(x%10+48);
}

LL mu[N+5]; int a, b, c, d, k;
void get_mu() {
    int isprime[N+5], prime[N+5], tot = 0;
    memset(isprime, 1, sizeof(isprime)); isprime[1] = 0, mu[1] = 1;
    for (int i = 2; i <= N; i++) {
    if (isprime[i]) mu[i] = -1, prime[++tot] = i;
    for (int j = 1; j <= tot && i*prime[j] <= N; j++)
        if (!(i%prime[j])) {isprime[i*prime[j]] = 0, mu[i*prime[j]] = 0; break; }
        else isprime[i*prime[j]] = 0, mu[i*prime[j]] = -mu[i];
    mu[i] += mu[i-1];
    }
}
LL cal(int x, int y) {
    if (x > y) Swap(x, y); LL ans = 0;
    for (int i = 1, last; i <= x; i = last+1) {
    last = Min(x/(x/i), y/(y/i));
    ans += (LL)(mu[last]-mu[i-1])*(x/i)*(y/i);
    }
    return ans;
}
void work() {
    read(a), read(b), read(c), read(d), read(k);
    writeln(cal(b/k, d/k)-cal(b/k, (c-1)/k)-cal((a-1)/k, d/k)+cal((a-1)/k, (c-1)/k));
}
int main() {
    int t; read(t); get_mu();
    while (t--) work();
    return 0;
}