HDU 4135 容斥原理

思路：

直接容斥

//By SiriusRen

#include <cstdio>

using namespace std;

#define int long long

const int N=;

int cases,a,b,n,tp,s[N];

int solve(int r){

    int ans=;

    for(int i=;i<(<<tp);i++){

        int tmp=,t=;

        for(int j=;j<tp;j++)

            if(i&(<<j))tmp*=s[j],t++;

        t=t&?:-;

        ans+=r/tmp*t;

    }

    return r-ans;

}

signed main(){

    scanf("%lld",&cases);

    for(int I=;I<=cases;I++){

        tp=;

        scanf("%lld%lld%lld",&a,&b,&n);

        for(int i=;i*i<=n;i++){

            if(n%i)continue;

            while(n%i==)n/=i;

            s[tp++]=i;

        }if(n!=)s[tp++]=n;

        printf("Case #%lld: %lld\n",I,solve(b)-solve(a-));

    }

}