容斥原理的(二进制思想和质因子分解+模板)hdu4135+ecf81.D

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

题意：求[A,B]与N互质的数的个数

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int M=1e5+5;
ll a[M];
ll A,B,N;
int tot;
void init(){
    tot=0;
    ll NN=N;
    for(int i=2;i*i<=NN;i++){
        if(N%i==0){
            a[tot++]=i;
            while(N%i==0)
                N/=i;
        }
    }
    if(N>1)
        a[tot++]=N;
}
ll solve(ll x){
    ll ans=0;
    for(ll i=1;i<((ll)1<<tot);i++){///枚举N的因子相乘子集 
        ll sum=1;
        int num=0;
        for(ll j=0;j<tot;j++){
            if(i&((ll)1<<j))
                sum*=a[j],num++;
        }
        ll tmp=x/sum;
        ///奇加偶减（容斥原理）
        ///ans为这些因子相乘能组成的数的个数（小于x）之和 
        if(num&1)
            ans+=tmp;
        else
            ans-=tmp;
    }
    return x-ans;
}
int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%lld%lld%lld",&A,&B,&N);
        init();

        printf("Case #%d: %lld
",i,solve(B)-solve(A-1ll));
    }
    return 0;
}

ecf：https://codeforces.com/contest/1295/problem/D

思路：https://www.cnblogs.com/heyuhhh/p/12243444.html

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int M=1e5+5;
ll a[M];
ll A,B;
int tot;
void init(ll N){
    tot=0;
    ll NN=N;
    for(ll i=2;i*i<=NN;i++){
        if(N%i==0){
            a[tot++]=i;
            while(N%i==0)
                N/=i;
        }
        if(i>N)
            break;
    }
    if(N>1)
        a[tot++]=N;
}
ll solve(ll x){
    ll ans=0;
    for(ll i=1;i<((ll)1<<tot);i++){
        ll sum=1;
        int num=0;
        for(ll j=0;j<tot;j++){
            if(i&((ll)1<<j))
                sum*=a[j],num++;
        }
        ll tmp=x/sum;
        if(num&1)
            ans+=tmp;
        else
            ans-=tmp;
    }
    return x-ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&A,&B);
        ll g=__gcd(A,B);
        A/=g;
        B/=g;
        init(B);
        printf("%lld
",solve(B+A-1)-solve(A-1));
    }
    return 0;
}