首页 > 代码库 > HDU 4135

HDU 4135

2024-08-01 19:46:16   216人阅读

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

求[A,B]内与N互素的数字个数

首先对N分解质因数，对于一个质因数，1-n与它不互素的数字个数是n/(这个质因数)，这样可以得到m个集合（m是N分解出的质因数的个数），对这m个集合用容斥原理解出来它们的并集，再用总数去减

这里学习了用位运算求解容斥原理，非常简单，和状压dp中的位运算差不多感觉，注意容斥中奇加偶减

#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;typedef __int64 ll;ll A,B,N;vector <ll> v;ll gao(ll n){    int m=v.size();    ll res=0;    for(int i=1;i<(1<<m);i++){        int cnt=0;        ll temp=1;        for(int j=0;j<m;j++){            if(i&(1<<j)){                cnt++;                temp*=v[j];            }        }        if(cnt&1)res+=n/temp;        else res-=n/temp;    }    return n-res;}int main(){    int T;    scanf("%d",&T);    for(int cas=1;cas<=T;cas++){        scanf("%I64d%I64d%I64d",&A,&B,&N);        v.clear();        for(ll i=2;i*i<=N;i++){            if(N%i==0){                v.push_back(i);                while(N%i==0)N/=i;            }        }        if(N>1)v.push_back(N);        printf("Case #%d: %I64d\n",cas,gao(B)-gao(A-1));    }    return 0;}
View Code

 

HDU 4135


联系
我们