hdu 1695 GCD 欧拉函数　＋　容斥

http://acm.hdu.edu.cn/showproblem.php?pid=1695

要求[L1, R1]和[L2, R2]中GCD是K的个数。那么只需要求[L1, R1 / K]  和 [L2, R2 / K]中GCD是1的对数。

由于(1， 2)和（2， 1）是同一对。

那么我们枚举大区间，限制数字一定是小于等于枚举的那个数字就行。

比如[1, 3]和[1, 5]

我们枚举大区间，[1, 5]，在[1, 3]中找互质的时候，由于又需要要小于枚举数字，那么直接上phi

对于其他的，比如4这样，在[1, 3]中找有多少个数字和它互质。

这需要容斥。先求不互质的个数，因为有个明显的道理，12 = 2 * 2 * 3，那么2的倍数可以排除，3的倍数可以排除，但是排除多了一部分。

区间中与i不互质的个数 = （区间中i的每个质因数的倍数个数）-（区间中i的每两个质因数乘积的倍数）+（区间中i的每3个质因数的成绩的倍数个数）-（区间中i的每4个质因数的乘积）

这个容斥好想但是不好写。我的dfs写的很烂。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn =  + ;
int prime[maxn];//这个记得用int，他保存的是质数，可以不用开maxn那么大
bool check[maxn];
int total;
bool is_prime[maxn];
int his[maxn][ + ];
int Size[maxn];
void initprime() {
    for (int i = ; i <= maxn - ; i++) {
        if (!check[i]) { //是质数了
            prime[++total] = i; //只能这样记录，因为后面要用
            is_prime[i] = true;
        }
        for (int j = ; j <= total; j++) { //质数或者合数都进行的
            if (i * prime[j] > maxn - ) break;
            check[i * prime[j]] = ;
            if (i % prime[j] == ) break;
            //关键，使得它只被最小的质数筛去。例如i等于6的时候。
            //当时的质数只有2,3,5。6和2结合筛去了12，就break了
            //18留下等9的时候，9*2=18筛去
        }
    }
//    Size[1] = 1;
//    his[1][1] = 1;
    for (int i = ; i <= maxn - ; ++i) {
        if (is_prime[i]) {
            Size[i] = ;
            his[i][] = i;
            continue;
        }
        int t = i;
        for (int j = ; j <= total; ++j) {
            if (prime[j] > t) break;
            if (t % prime[j] == ) {
                his[i][++Size[i]] = prime[j];
                t /= prime[j];
                while (t % prime[j] == ) {
                    t /= prime[j];
                }
            }
        }
    }
    return ;
}
int phi[maxn];
void init_phi() {
    phi[] = ;
    for (int i = ; i <= maxn - ; i++) {
        if (!phi[i]) {
            for (int j = i; j <= maxn - ; j += i) {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - );
            }
        }
    }
    return ;
}
LL calc(int up, int cur, int number, int tobuild, int flag) {
    LL ans = ;
    for (int i = cur; i <= Size[number]; ++i) {
        if (flag == ) {
            ans += up / (his[number][i] * tobuild) + calc(up, i + , number, tobuild * his[number][i], !flag);
        } else ans += -up / (his[number][i] * tobuild) + calc(up, i + , number, tobuild * his[number][i], !flag);
    }
    return ans;
}
int f;
void work() {
    int L1, R1, L2, R2, k;
    scanf("%d%d%d%d%d", &L1, &R1, &L2, &R2, &k);
    if (k == ) {
        printf("Case %d: 0\n", ++f);
        return;
    }
    R1 /= k;
    R2 /= k;
    if (R1 < R2) swap(R1, R2);
    LL ans = ;
    for (int i = ; i <= R2; ++i) {
        ans += phi[i];
    }
    for (int i = R2 + ; i <= R1; ++i) {
        ans += R2 - calc(R2, , i, , );
    }
    printf("Case %d: %I64d\n", ++f, ans);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    initprime();
    init_phi();
//    cout << 24 - calc(24, 1, 12, 1, 0) << endl;
//    cout << 12 - calc(12, 1, 12, 1, 0) << endl;
//    for (int i = 1; i <= Size[10]; ++i) {
//        printf("%d ", his[10][i]);
//    }
    int t;
    scanf("%d", &t);
    while (t--) {
        work();
    }
    return ;
}