hdu 1695 GCD

           容斥原理 + 欧拉函数 或 莫比乌斯反演。莫比乌斯反演要比容斥原理快的多。。

           先说一下容斥原理的思路吧。其实容斥原理方法挺暴力的，本来一直想一次容斥就把结果算出来的，未果。。然后没办法了想到，对于每一个c < x < d， 求小于x且小于等于b的所有互质的个数（d > b），然后相加就行了。注意case组数有3000之多，所以要先把每个数质因子初始化出来，不然会超时！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int M = 100001;

vector<int> hav[M];
LL has[M];
LL phi[M];

void get_phi()
{
    int i, j;
    phi[1] = 1;has[0] = 0;has[1] = 1;
    for(i = 2; i < M; i ++)
    {
        if(!phi[i])
        {
            for(j = i; j < M; j += i)
            {
                if(!phi[j])
                    phi[j] = j;
                phi[j] -= phi[j] / i;
                hav[j].push_back(i);
            }
        }
        has[i] = has[i-1] + phi[i];
    }
}

int dfs(int u, int c, int b, int di)
{
    int ret = 0, sz = hav[di].size();
    if(c > b) return 0;
    for(; u < sz; u ++)
    {
        ret += b / (hav[di][u] * c) - dfs(u + 1, c * hav[di][u], b, di);
    }
    return ret;
}


int main()
{
    //freopen("input.txt", "r", stdin);
    int cas = 1, t, i;
    int a, b, c, d, k, flag;LL ans;
    get_phi();
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        flag = 0;ans = 0;
        if(k == 0)
        {
            printf("Case %d: %d
", cas ++, ans);
            continue;
        }
        if(b > d) swap(b, d);
        b /= k; d /= k;
        ans = has[b];
        for(i = b + 1; i <= d; i ++)
        {
            ans += (b - dfs(0, 1, b, i));
        }
        printf("Case %d: %I64d
", cas ++, ans);
    }
}