hdu 1695 欧拉函数 + 容斥原理

分析：

本质是求区间内与某个数互质的数的个数，如果区间比这个数小用欧拉函数。比这个数大用全集减去不互质的个数。不互质的个数的计算方法是对当前数进行因数分解，然后求能被 p1∪p2∪......∪pn 整除的数的个数，显然用容斥。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  " 
#define pl(x) cout << #x << ": " << x << endl;
typedef long long ll;
const int maxn = int() + ;
struct jibancanyang
{
    int b, d, k;
    ll elur[maxn], factors[maxn][];

    void getElur() {
        memset(elur, , sizeof(elur));
        memset(factors, , sizeof(factors));
        elur[] = ;
        for (int i = ; i < maxn; ++i) {
            if (!elur[i]) {
                for (int j = i; j < maxn; j += i) {
                    if (!elur[j]) elur[j] = j;
                    factors[j][++factors[j][]] = i;
                    elur[j] = elur[j] * (i - ) / i;
                }
            }
           // elur[i] += elur[i - 1];
        }
    }

    int doit(int limit, int x) {
        ll ret = ;
        for (int s = ; s <  << factors[x][]; ++s) {
            int cur = , cnt = ;
            for (int  i = ; i < factors[x][]; ++i) {
                if (s >> i & ) ++cnt, cur *= factors[x][i + ];
            }
            if (cnt & ) ret += limit / cur;
            else ret -= limit / cur;
        }
        return (int)ret;
    }

    void fun() {
        int T, a, c, k;
        scanf("%d", &T);
        for (int cas = ; cas <= T; ++cas) {
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
            if (k == ) {
                printf("Case %d: 0\n", cas);
                continue;
            }
            b /= k, d /= k;
            ll ans = ;
            if (b > d) swap(b, d);
            for (int i = d; i >= ; --i) {
                if (b >= i) ans += elur[i];
                else {
                    ans += b - doit(b, i);
                }
            }
            printf("Case %d: %lld\n", cas, ans);
        }
    }
}ac;


int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    ac.getElur();
    ac.fun();
    return ;
}