Cod sursa(job #541641)

Utilizator LgregL Greg Lgreg Data 25 februarie 2011 12:48:28
Problema Light2 Scor 80
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 0.86 kb
#include<stdio.h>

long long N,K,v[203],q,rez;
inline long long euc(long long a,long long b)
{
if(b==0) return a;
else return euc(b,a%b);
}
inline long long cmmmc(long long a,long long b)
{
    return a*b/euc(a,b);
}
inline void desc(long long x)
{
    long long k=1;
    long long S=1;
    long long P=1;
    q=0;
    while(x)
    {//printf("%d",x%2);
        if(x%2==1)
        {++q;
        if(q==1)
            S=v[k];
            else
         S=cmmmc(S,v[k]);

        }
        x=x/2;
         ++k;
    }



    if(q%2==1)
    rez+=(N/S)*(1<<(q-1));
    else rez-=(N/S)*(1<<(q-1));

}

int main()
{
freopen("light2.in","r",stdin);
freopen("light2.out","w",stdout);
scanf("%lld%lld",&N,&K);
for(int i=1;i<=K;++i)
    scanf("%lld",&v[i]);

for(int i=1;i<=(1<<K)-1;++i)
    {
        desc(i);
    }
    printf("%lld\n",rez);
}