题目链接：

题目大意：求[1..b]中的x和[1..d]中的y有多少gcd(x,y) = k.

思路： 预备知识：

容斥原理求数区间[1..r]中与n互质的数的个数.  

要求gcd(x,y) = k，则等价于求 gcd(x/k,y/k) = 1.所以问题转化成求[1..b/k]和[1..d/k]中有多少对gcd(x,y) = 1. 又因为此题要求gcd(1,3)和gcd(3,1)算一个，所以我们不妨按x < y来求. 接下来，我们枚举x的值，然后便转化为求[x..d/k]区间中与x互质的数的个数，用容斥原理解决. [x..d/k] = [1..d/k] - [1..x-1]，[1..d/k]我们用上面的容斥原理方法就可以解决，[1..x-1]虽然也可以用容斥，但速度较慢，明显可以用更快的欧拉函数做。  

#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)using namespace std;typedef long long LL;    //max long long == 9223372036854775807LLLL phi(LL n){    if (n == 1) return 0;    LL i,sum=n;    for(i=2; i*i<=n; i++)    {        if(n%i==0)        {            sum = sum / i * (i-1);            do            {                n/=i;            }            while(n%i==0);        }    }    if(n>1) sum = sum / n * (n - 1);    return sum;}int solve(int r, int n){    if (r == 0) return 0;    int res = 0;    vector  p;    for (int i = 2; i * i <= n; i ++){        if (n % i == 0){            p.push_back(i);            while(n % i == 0){                n /= i;            }        }        if (n == 1) break;    }    if (n > 1)  p.push_back(n);    for (int msk = 1; msk < (1 << p.size()); msk ++){        int mult = 1, bit = 0;        for (int i = 0; i < p.size(); i ++){            if (msk & (1 << i)){                bit ++;                mult *= p[i];            }        }        int cur = r / mult;        if (bit % 2 == 1){            res += cur;        }        else{            res -= cur;        }    }    return r - res;}int main(){    int t, caseo = 1;    cin>>t;    while(t --){        int a,b,c,d,k;        cin>>a>>b>>c>>d>>k;        if (k == 0){            cout< d){            int tmp = d;            d = b;            b = tmp;        }        LL ans = 0;        for (int i = 1; i <= b; i ++){            ans += (LL)solve(d, i) - phi(i);        }        cout<