容斥原理——hdu1796

佚名 6年前 (2019-05-14) 随笔 1518人围观抢沙发百度已收录

/*
遇到这种题一般用dfs，枚举起点来做
但是本题如何进行容斥？
比如以x为起点，第一步dfs到y，那么因子有lcm(x,y)的 所有数要被减掉(容斥中偶数是减法) 
然后第二步dfs到z，那么因子有lcm(x,y,z)的所有数要加上(容斥) 
*/ 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1<<31
ll n,m,p[30],ans;

void dfs(int pos,ll LCM,ll cnt){
    if(p[pos]==0)return;
    ll d=__gcd(LCM,p[pos]);
    LCM=LCM*p[pos]/d;//求出新的lcm 
    if(cnt%2)ans+=(n-1)/LCM;//容斥，注意是<n 
    else ans-=(n-1)/LCM;
    for(int i=pos+1;i<=m;i++)dfs(i,LCM,cnt+1);
}

int main(){
    while(cin>>n>>m){
        ans=0;
         for(int i=1;i<=m;i++)cin>>p[i];
         for(int i=1;i<=m;i++)dfs(i,p[i],1); 
        cout<<ans<<endl;
    }
}