1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 __int64 n,m,g; 7 __int64 a[1000],b[1000]; 8  9 __int64 gcd(__int64 a,__int64 b)10 {11     return b==0?a:gcd(b,a%b);12 }13 14 int main()15 {16     while(scanf("%I64d%I64d",&n,&m)!=EOF)17     {18         memset(a,0,sizeof(a));19         __int64 cnt=0;20         for(int i=0; i<m; i++)21         {22             __int64 x;23             scanf("%I64d",&x);24             if(x)25             a[cnt++]=x;26         }27         __int64 ans=0;28         for(int i=1; i<(1<<cnt); i++)29         {30             __int64 xx=0;31             __int64 x=1;32             memset(b,0,sizeof(b));33             for(int j=0; j<cnt; j++)34             {35                 if(i&(1<<j))36                 {37                     b[xx]=a[j];38                     xx++;39                     x*=a[j];40                 }41             }42             if(xx>1)43             {44                 g=(b[0]*b[1])/gcd(b[0],b[1]);45                 for(int k=2; k<xx; k++)46                 {47                     g=(g*b[k])/gcd(g,b[k]);48                 }49                 x=g;50             }51             if(xx%2!=0)52             {53                 ans+=((n-1)/x);54             }55             else56             {57                 ans-=((n-1)/x);58             }59         }60         printf("%I64d\n",ans);61     }62     return 0;63 }