题目：
思路：
题意让求:
f
(
k
)
=
∑
x
=
A
B
∑
y
=
C
D
[
g
c
d
(
x
,
y
)
=
k
]
f(k)=\sum_{x=A}^B\sum_{y=C}^D[gcd(x,y)=k]
f(k)=∑x=AB∑y=CD[gcd(x,y)=k]
为了满足：
F
(
k
)
=
∑
n
∣
d
f
(
d
)
F(k)=\sum_{n|d}f(d)
F(k)=∑n∣df(d)
设：
F
(
k
)
=
∑
x
=
A
B
∑
x
=
C
D
[
k
∣
g
c
d
(
x
,
y
)
]
F(k)=\sum_{x=A}^B\sum_{x=C}^D[k|gcd(x,y)]
F(k)=∑x=AB∑x=CD[k∣gcd(x,y)]
为使枚举的
x
,
y
x,y
x,y均为
k
k
k的倍数
令
x
′
=
x
k
,
y
′
=
y
k
x' = \frac xk,\quad y' = \frac yk
x′=kx,y′=ky，我们枚举倍数
则
F
(
k
)
=
∑
x
′
=
A
−
1
k
B
k
∑
y
′
=
C
−
1
k
D
k
=
(
⌊
B
k
⌋
−
⌊
A
−
1
k
⌋
)
∗
(
⌊
D
k
⌋
−
⌊
C
−
1
k
⌋
)
F(k)=\sum_{x'=\frac{A - 1}{k}}^{\frac Bk}\sum_{y'=\frac{C-1}{k}}^{\frac Dk}=(\left \lfloor \frac Bk \right \rfloor-\left \lfloor \frac{A-1}k \right \rfloor)*(\left \lfloor \frac Dk\right \rfloor -\left \lfloor \frac{C-1}k \right \rfloor)
F(k)=∑x′=kA−1kB∑y′=kC−1kD=(⌊kB⌋−⌊kA−1⌋)∗(⌊kD⌋−⌊kC−1⌋)
根据莫比乌斯反演定理得：
f
(
k
)
=
∑
k
∣
d
μ
(
d
k
)
F
(
d
)
f(k)=\sum_{k|d}\mu(\frac dk)F(d)
f(k)=∑k∣dμ(kd)F(d)
为了使枚举到的d均为k的倍数
我们设
d
′
=
d
k
H
′
=
H
k
d' = \frac dk\quad H'=\frac Hk
d′=kdH′=kH，此时
d
=
d
′
k
d=d'k
d=d′k
则 f ( k ) = ∑ d ′ = 1 m i n ( B k , D k ) μ ( d ′ ) F ( d ′ k ) f(k)=\sum_{d'=1}^{min(\frac Bk,\frac Dk)}\mu(d')F(d'k) f(k)=∑d′=1min(kB,kD)μ(d′)F(d′k)
∵ F ( d ′ k ) = ( ⌊ B d ′ k ⌋ − ⌊ A − 1 d ′ k ⌋ ) ∗ ( ⌊ D d ′ k ⌋ − ⌊ C − 1 d ′ k ⌋ \because F(d'k)=(\left \lfloor \frac B{d'k} \right \rfloor-\left \lfloor \frac{A-1}{d'k} \right \rfloor)*(\left \lfloor \frac D{d'k}\right \rfloor -\left \lfloor \frac{C-1}{d'k} \right \rfloor ∵F(d′k)=(⌊d′kB⌋−⌊d′kA−1⌋)∗(⌊d′kD⌋−⌊d′kC−1⌋
令 A ′ = A − 1 k , B ′ = B k , C ′ = C − 1 k , D ′ = D k A'=\frac{A-1}k,\quad B'=\frac Bk,\quad C'=\frac{C-1}k,\quad D'=\frac Dk A′=kA−1,B′=kB,C′=kC−1,D′=kD
∴ f ( k ) = ∑ d ′ = 1 m i n ( B ′ , D ′ ) μ ( d ′ ) ( ⌊ B ′ d ′ ⌋ − ⌊ A ′ d ′ ⌋ ) ( ⌊ D ′ d ′ ⌋ − ⌊ C ′ d ′ ⌋ \therefore f(k)=\sum_{d'=1}^{min(B',D')}\mu(d')(\left \lfloor \frac {B'}{d'} \right \rfloor-\left \lfloor \frac{A'}{d'} \right \rfloor)(\left \lfloor \frac {D'}{d'}\right \rfloor -\left \lfloor \frac{C'}{d'} \right \rfloor ∴f(k)=∑d′=1min(B′,D′)μ(d′)(⌊d′B′⌋−⌊d′A′⌋)(⌊d′D′⌋−⌊d′C′⌋
代码：
/*
________ _ ________ _
/ ______| | | | __ | | |
/ / | | | |__| | | |
| | | |___ _ _ _ ___ _ _____ | ___| ______ _____ ___ _ | |
| | | __ \ |_| | | | | | _\| | | ____| | |\ \ | __ | | _ | | _\| | | |
| | | | \ | _ | | | | | | \ | | \___ | | \ \ | |_/ _| | |_| | | | \ | | |
\ \______ | | | | | | \ |_| / | |_/ | ___/ | | | \ \ | /_ \__ | | |_/ | | |
Author : \________| |_| |_| |_| \___/ |___/|_| |_____| _________|__| \__\ |______| | | |___/|_| |_|
____| |
\_____/
*/
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define G 10.0
#define LNF 1e18
#define EPS 1e-6
#define PI acos(-1.0)
#define INF 0x7FFFFFFF
#define ll long long
#define ull unsigned long long
#define LOWBIT(x) ((x) & (-x))
#define LOWBD(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
#define UPPBD(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
#define TEST(a) cout << "---------" << a << "---------" << '\n'
#define CHIVAS_ int main()
#define _REGAL exit(0)
#define SP system("pause")
#define IOS ios::sync_with_stdio(false)
//#define map unordered_map
#define push_back emplace_back
#define _int(a) int a; cin >> a
#define _ll(a) ll a; cin >> a
#define _char(a) char a; cin >> a
#define _string(a) string a; cin >> a
#define _vectorInt(a, n) vector<int>a(n); cin >> a
#define _vectorLL(a, b) vector<ll>a(n); cin >> a
#define PB(x) push_back(x)
#define ALL(a) a.begin(),a.end()
#define MEM(a, b) memset(a, b, sizeof(a))
#define EACH_CASE(cass) for (cin >> cass; cass; cass--)
#define LS l, mid, rt << 1
#define RS mid + 1, r, rt << 1 | 1
#define GETMID (l + r) >> 1
using namespace std;
template<typename T> inline void Read(T &x){T f = 1; x = 0;char s = getchar();while(s < '0' || s > '9'){if(s == '-') f = -1; s = getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;}
template<typename T> inline T MAX(T a, T b){return a > b? a : b;}
template<typename T> inline T MIN(T a, T b){return a > b? b : a;}
template<typename T> inline void SWAP(T &a, T &b){T tp = a; a = b; b = tp;}
template<typename T> inline T GCD(T a, T b){return b > 0? GCD(b, a % b) : a;}
template<typename T> inline void ADD_TO_VEC_int(T &n, vector<T> &vec){vec.clear(); cin >> n; for(int i = 0; i < n; i ++){T x; cin >> x, vec.PB(x);}}
template<typename T> inline pair<T, T> MaxInVector_ll(vector<T> vec){T MaxVal = -LNF, MaxId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MaxVal < vec[i]) MaxVal = vec[i], MaxId = i; return {MaxVal, MaxId};}
template<typename T> inline pair<T, T> MinInVector_ll(vector<T> vec){T MinVal = LNF, MinId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MinVal > vec[i]) MinVal = vec[i], MinId = i; return {MinVal, MinId};}
template<typename T> inline pair<T, T> MaxInVector_int(vector<T> vec){T MaxVal = -INF, MaxId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MaxVal < vec[i]) MaxVal = vec[i], MaxId = i; return {MaxVal, MaxId};}
template<typename T> inline pair<T, T> MinInVector_int(vector<T> vec){T MinVal = INF, MinId = 0;for(int i = 0; i < (int)vec.size(); i ++) if(MinVal > vec[i]) MinVal = vec[i], MinId = i; return {MinVal, MinId};}
template<typename T> inline pair<map<T, T>, vector<T> > DIV(T n){T nn = n;map<T, T> cnt;vector<T> div;for(ll i = 2; i * i <= nn; i ++){while(n % i == 0){if(!cnt[i]) div.push_back(i);cnt[i] ++;n /= i;}}if(n != 1){if(!cnt[n]) div.push_back(n);cnt[n] ++;n /= n;}return {cnt, div};}
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
const ll maxn = 2e6 + 10;//杜教筛的安全maxn
ll mu[maxn];//Mobius函数表
vector<ll> prime;
ll isprime[maxn];
ll sum[maxn];//mu的前缀和
inline void Mobius(){//线性筛
mu[1] = 1;//特判mu[i] = 1
isprime[0] = isprime[1] = 1;
for(ll i = 2; i < maxn; i ++){
if(!isprime[i]) mu[i] = -1, prime.push_back(i);//质数的质因子只有自己，所以为-1
for(ll j = 0; j < prime.size() && i * prime[j] < maxn; j ++){
isprime[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
mu[i * prime[j]] = - mu[i];//积性函数性质： (i * prime[j])多出来一个质数因数(prime[j])，修正为 (-1) * mu[i]
}
}
//剩余的没筛到的是其他情况，为0
for(ll i = 1; i < maxn; i ++) sum[i] = sum[i - 1] + mu[i];//记录前缀和，为了整除分块
}
inline ll g(ll k, ll x){ return k / (k / x); }//整除分块的r值
map<ll, ll> S;//杜教筛处理出的前缀和
inline ll SUM(ll x){//杜教筛
if(x < maxn) return sum[x];
if(S[x]) return S[x];
ll res = 1;
for(ll L = 2, R; L <= x; L = R + 1){
R = MIN(x, g(x, L));
res -= (R - L + 1) * SUM(x / L);//模数相减会出负数，所以加上一个mod
}return S[x] = res;
}
inline void solve(){
ll A, B, C, D, K; cin >> A >> B >> C >> D >> K;
A = (A - 1) / K, B = B / K, C = (C - 1) / K, D = D / K;
ll n = MIN(B, D);
ll res = 0;
for(ll l = 1, r; l <= n; l = r + 1){
ll cmp1 = (A / l)? MIN(g(A, l), g(B, l)) : g(B, l);//防止除0
ll cmp2 = (C / l)? MIN(g(C, l), g(D, l)) : g(D, l); //防止除0
r = MIN(cmp1, cmp2);//确定块右端点
res += (sum[r] - sum[l - 1]) * (B / l - A / l) * (D / l - C / l);//公式
}cout << res << endl;
}
CHIVAS_{Mobius();
ll cass;
EACH_CASE(cass){
solve();
}
_REGAL;
}