/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=15&problem=1266&mosmsg=Submission+received+with+ID+11830997
容斥原理 第一题 水！
代码：
#include<iostream>#include<cstring>#include<cstdio>#include<string>#include<set>#include<map>#include<cmath>#include<algorithm>#include<vector>#include<cmath>#include<queue>#include<stack>//#define ull unsigned long long#define ll long longusing namespace std;const int INF=0x3f3f3f3f;const int MOD=1000000007;const double eps=1e-6;const int N=50;ll gcd(ll x,ll y){if(x%y==0)return y;return gcd(y,x%y);}ll lcm(ll x,ll y){return x*y/gcd(x,y);}ll a[N];ll solve(ll *a,int n,ll M){ll sum=0;for(int k=1;k<(1<<n);++k){ll LCM=1;int num=0;for(int i=0;i<n;++i){if(k&(1<<i)){++num;LCM=lcm(LCM,a[i]);}}if((num&1)==1){sum+=(M/LCM);}else{sum-=(M/LCM);}}return sum;}int main(){//freopen("data.in","r",stdin);ll n;int m;while(cin>>n>>m){for(int i=0;i<m;++i)cin>>a[i];cout<<(n-solve(a,m,n))<<endl;}return 0;}
