<题目链接 https://vjudge.net/contest/282814#problem/B>
题目大意:
给你 m 个数, 其中可能含有 0, 问有多少小于 n 的正数能整除这个 m 个数中的某一个.
解题分析:
容斥水题, 直接对这 m 个数 (除 0 以外) 及其组合的倍数在 [1,n) 中的个数即可, 因为可能会重复计算, 所以在叠加的时候进行容斥处理, 下面用的是位运算实现容斥.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- ll n,m,arr[15];
- ll gcd(ll a,ll b){
- return b==0?a:gcd(b,a%b);
- }
- ll lcm(ll a,ll b){
- return a*b/gcd(a,b);
- }
- int main(){
- while(cin>>n>>m){
- int cnt=0;
- for(int i=1;i<=m;i++){
- scanf("%lld",&arr[cnt]);
- if(arr[cnt])cnt++;
- }
- ll sum=0;
- for(int i=1;i<(1<<cnt);i++){
- ll res=1,tot=0;
- for(int j=0;j<cnt;j++){
- if(i & (1<<j)){
- res=lcm(res,arr[j]); // 注意这里将不同的数组合时, 是求它们的 lcm, 而不是直接相乘
- tot++; // 组合的数个数, 用于后面判奇偶
- }
- }
- if(tot & 1)sum+=(n-1)/res; // 题意不包含 n
- else sum-=(n-1)/res;
- }
- printf("%lld\n",sum);
- }
- }
- 2019-02-09
来源: http://www.bubuko.com/infodetail-2948945.html