容斥原理。自己水吧。
#include<bits/stdc++.h>
inline const void read(long long &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
inline const void write(long long a)
{
if(a>9)write(a/10);
putchar(a%10+'0');
}
inline const long long gcd(long long a,long long b)
{
if(a<b)return gcd(b,a);
if(!b)return a;
return gcd(b,a%b);
}
inline const long long lcm(long long a,long long b)
{
return a/gcd(a,b)*b;
}
long long n,m,a[21],ans=0;
int main()
{
read(n);read(m);
for(long long i=1;i<=m;i++)read(a[i]);
long long p,d;
for(long long i=1;i<=(1<<m)-1;i++)
{
p=1;d=-1;
for(long long j=1;j<=m;j++)
{
if(i&(1<<(j-1)))
{
d*=-1;
p=lcm(p,a[j]);
if(p>n){p=0;break;}
}
}
if(p)ans+=d*n/p;
}
write(n-ans);
return 0;
}