HDU 4135 Co-prime 容斥原理

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4135

　　题目描述：给你A， B， N，让你求A到B之间与N互质的数的个数

　　解题思路：容斥原理，先将N质因数分解，然后对每一个质因子做容斥即可

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

ll a, b, n;
ll t[100];
ll ans;
int cnt;

void init( ll num ) {

    for( ll i = 2; i * i <= num; i++ ) {
        if( num % i == 0 ) {
            t[cnt++] = i;
            while( num % i == 0 ) {
                num /= i;
            }
        }
    }
    if( num > 1 ) {
        t[cnt++] = num;
    }
}

ll func( ll m ) {
    ll ret = 0;
    for( ll i = 1; i < (1<<cnt); i++ ) {
        ll val = 1;
        int temp = 0;
        for( int j = 0; j < cnt; j++ ) {
            if( i & (1 << j) ) {
                val *= t[j];
                temp++;
            }

        }
        if( temp & 1 ) {
            ret += m / val;
        }
        else {
            ret -= m / val;
        }
    }
    return m-ret;
}
int main() {
    int t;
    sca(t);
    int cases = 1;
    while( t-- ) {
        scanf( "%lld%lld%lld", &a, &b, &n );
        
        ans = 0;
        cnt = 0;
        init( n );
        printf( "Case #%d: %lld
", cases++, func(b)-func(a-1) );
    }
    return 0;
}

View Code

　　思考：这次的容斥原理用的是位运算的容斥，每一位表示的是当前这个素因子有没有用到......今天删了写了好长时间写的代码......对，不是故意删的.....要学习git了......