/* 遇到这种题一般用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; } }