当前位置: 代码迷 >> 综合 >> 容斥模板
  详细解决方案

容斥模板

热度:80   发布时间:2024-01-14 22:26:34.0
//判断1-n有多少个M个因子任一个的倍数
int n,m,cnt;
ll ans ,a[30];
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}void DFS(int cur,ll lcm,int id)  
{// 当前第几个因子  这些因子的最小共公倍数 当前总因子lcm = a[cur]/gcd(a[cur],lcm)*lcm;if(id&1)   //奇加偶减ans += (n-1)/lcm;elseans -= (n-1)/lcm;for(int i= cur+1;i<cnt;i++)DFS(i,lcm,id+1);
}
int main()
{while(scanf("%d%d",&n,&m) != EOF){cnt = 0;int x;while(m--){scanf("%d",&x);if(x!=0)a[cnt++] = x;}ans = 0;for(int i=0;i<cnt;i++) //遍历每种组合 从1开始DFS(i,a[i],1);printf("%lld\n",ans);}return 0;
}
//判断1-n 有多少个符合m^k的数
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll ans ,n;
void dfs(int cur,int s,int cnt)
{ll t = (ll)pow(n,1.0/s);if(t>1){if(cnt&1)ans += t-1;elseans -= t-1;}if(cnt>2) return ;for(int i = cur+1;i<17;i++)dfs(i,s*p[i],cnt+1);
}
int main()
{while(scanf("%lld",&n) != EOF){ans = 1;for(int i=0;i<17;i++)// 最大2^59 2^(2*3*5)dfs(i,p[i],1);cout<<ans<<endl;}return 0;
}

 

 

  相关解决方案