容斥原理的两道题

HDU  1695  GCD

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=100000+5;
int a,b,c,d,k;
bool isprime[maxn];
int prime[maxn];
int cnt=0;
long long phi[maxn];

struct Num {
    int factor[30];
    int idx;
} num[maxn];

void init() {
    memset(isprime,true,sizeof(isprime));
    for(int i=2; i<maxn; i++) {
        if(isprime[i]) {
            prime[cnt++]=i;
            for(int j=2*i; j<maxn; j+=i)
                isprime[j]=false;
        }
    }
    for(int i=1; i<maxn; i++) {
        phi[i]=i;
        num[i].idx=0;
    }
    num[1].factor[num[1].idx++]=1;
    for(int i=2; i<maxn; i++) {
        if(isprime[i]) {
            for(int j=i; j<maxn; j+=i) {
                phi[j]=phi[j]/i*(i-1);
                num[j].factor[num[j].idx++]=i;
            }
        }
    }
    for(int i=2; i<maxn; i++)
        phi[i]+=phi[i-1];

}
//容斥原理，太奇妙了！
long long rongchi(int n,int m,int idx) {
    long long ret=0,tmp;
    for(int i=idx; i<num[n].idx; i++) {
        tmp=(long long)m/num[n].factor[i];
        ret+=tmp-rongchi(n,tmp,i+1);
    }
    return ret;
}
/*
long long rongchi(int index,int m,int n) {
    //index表示此刻算到n的哪个质因数，m表示在1~b中计算能被某质因数整除的个数，n指[bk+1,dk]区间的数。
    long long ans=0,tmp;
    for(int i=index;i<num[n].cnt;i++) { //x与y的最大公约数为k*p(p为质数)
        tmp=m/num[n].prime[i];    //w是n的素因子，则（1,b）中是w倍数的数共有b/w个
        ans+=tmp-rongchi(i+1,tmp,n);  //因为防止有数被重复计算，所以根据容斥定理
    }
    return ans;
}
*/
int main() {
    int t,cases=0;
    init();
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k) {
            //注意k不能为0
            b=b/k;
            d=d/k;
            if(b>d)
                swap(b,d);
            long long ans=phi[b];
            for(int i=b+1; i<=d; i++) {
                ans+=(b-rongchi(i,b,0));
            }
            printf("Case %d: %I64d
",++cases,ans);
        } else {
            //当k=0的时候，结果为0。。。
            printf("Case %d: 0
",++cases);
        }
    }
    return 0;
}

HDU 4336 Card Collector

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn=21;
double prob[maxn];
int n;
double ans=0;
//容斥原理  AC
//k表示目前从第k张卡片开始考虑，p是目前考虑过的卡片的概率和
double rongchi(int k,double p){
    double ret=0,tmp,pp;
    for(int i=k;i<n;i++){
        pp=p+prob[i];
        tmp=1/pp;
        ret+=tmp-rongchi(i+1,pp);
    }
    return ret;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        ans=0;
        for(int i=0;i<n;i++)
            scanf("%lf",&prob[i]);
        printf("%.4lf
",rongchi(0,0));
    }
    return 0;
}