Cod sursa(job #966294)

Utilizator geniucosOncescu Costin geniucos Data 25 iunie 2013 17:49:52
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
using namespace std;
int sumexp,i,j,n,m,mi,nr,pr[100009];
char cr[1000009];
long long cnt;
void back(long long val,int p)
{
    int i;
    long long vv;
    if(sumexp&1) cnt-=1LL*(n/val)*(m/val);
    else cnt+=1LL*(n/val)*(m/val);
    for(i=p;i<=nr;i++)
    {
        vv=val*pr[i];
        if(vv<=mi)
        {
            sumexp++;
            back(vv,i+1);
            sumexp--;
        }
        else return ;
    }
}
int main()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
n--;m--;
mi=n;
if(m<mi) mi=m;
for(i=2;i*i<=mi;i++)
    if(cr[i]==0)
    {
        for(j=i*i;j<=mi;j+=i)
            cr[j]=1;
    }
for(i=2;i<=mi;i++)
    if(cr[i]==0){nr++;pr[nr]=i;}
back(1,1);
printf("%lld\n",cnt);
return 0;
}