Description

Input

Output

Sample Input

Sample Output

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)~~(i\in[1,x],j\in[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}^{\left\lfloor\frac{a}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor\frac{b}{k} \right\rfloor}[gcd(i,j)=1]$$

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

$$\Rightarrow \sum_{i=1}^{\left\lfloor\frac{a}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor\frac{b}{k} \right\rfloor}\sum_{d\mid gcd(i,j)}\mu(d)$$

我们将 $\mu$ 提前

\begin{aligned} &\Rightarrow\sum_{d=1}^{min\left\{\left\lfloor\frac{a}{k} \right\rfloor,\left\lfloor\frac{b}{k} \right\rfloor\right\}}\mu(d)\sum_{i=1,d\mid i}^{\left\lfloor\frac{a}{k} \right\rfloor}\sum_{j=1,d\mid j}^{\left\lfloor\frac{b}{k}\right\rfloor}1\\&\Rightarrow\sum_{d=1}^{min\left\{\left\lfloor\frac{a}{k} \right\rfloor,\left\lfloor\frac{b}{k} \right\rfloor\right\}}\mu(d)\cdot\left\lfloor\frac{\left\lfloor\frac{a}{k}\right\rfloor}{d}\right\rfloor\cdot\left\lfloor\frac{\left\lfloor\frac{b}{k}\right\rfloor}{d}\right\rfloor\end{aligned}

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

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

由题 $$F(k)=\sum_{d=1}^{min\left\{\left\lfloor\frac{a}{k}\right\rfloor,\left\lfloor\frac{b}{k} \right\rfloor\right\}}f(kd)$$

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

\begin{aligned}\Rightarrow f(k)&=\sum_{d=1}^{min\left\{\left\lfloor\frac{a}{k}\right\rfloor,\left\lfloor\frac{b}{k}\right\rfloor\right\}}\mu(d)F(kd)\\&=\sum_{d=1}^{min\left\{\left\lfloor\frac{a}{k} \right\rfloor,\left\lfloor\frac{b}{k}\right\rfloor\right\}}\mu(d)\cdot\left\lfloor\frac{a}{kd}\right\rfloor\cdot\left\lfloor\frac{b}{kd}\right\rfloor\end{aligned}

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

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

证明：

　　1.当 $1\leq d < \sqrt n$ 时， $d$ 就只有 $\sqrt n$ 个， $\left\lfloor{n \over d}\right\rfloor$ 最多有 $\sqrt n$ 个。

　　2.当 $\sqrt n \leq d \leq n$ 时，由于 $\left\lfloor{n \over d}\right\rfloor$ 小于 $\sqrt n$ ，所以 $\left\lfloor{n \over d}\right\rfloor$ 最多有 $\sqrt n$ 个。

证毕。

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

证明：

对于 $n$ 来说，找到最大的 $j$ 满足 $$\left\lfloor\frac{n}{i}\right\rfloor \leq\left\lfloor\frac{n}{j}\right\rfloor$$

化简一下得到 $$j\leq \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$$

那么在计算时在分别关于 $a, b$ 的表达式中取一个较小值即可。时间复杂度 $O(n\sqrt 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('\n'))

 using namespace std;

 const int N = ;

 const int INF = ~0u>>;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(LL x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 LL mu[N+]; int a, b, c, d, k;

 void get_mu() {

     int isprime[N+], prime[N+], tot = ;

     memset(isprime, , sizeof(isprime)); isprime[] = , mu[] = ;

     for (int i = ; i <= N; i++) {

     if (isprime[i]) mu[i] = -, prime[++tot] = i;

     for (int j = ; j <= tot && i*prime[j] <= N; j++)

         if (!(i%prime[j])) {isprime[i*prime[j]] = , mu[i*prime[j]] = ; break; }

         else isprime[i*prime[j]] = , mu[i*prime[j]] = -mu[i];

     mu[i] += mu[i-];

     }

 }

 LL cal(int x, int y) {

     if (x > y) Swap(x, y); LL ans = ;

     for (int i = , last; i <= x; i = last+) {

     last = Min(x/(x/i), y/(y/i));

     ans += (LL)(mu[last]-mu[i-])*(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-)/k)-cal((a-)/k, d/k)+cal((a-)/k, (c-)/k));

 }

 int main() {

     int t; read(t); get_mu();

     while (t--) work();

     return ;

 }