Cod sursa(job #966285)

Utilizator geniucosOncescu Costin geniucos Data 25 iunie 2013 17:28:50
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<cstdio>
using namespace std;
int i,j,n,m,mi,nr,pr[50009];
char cr[1000009];
long long cnt;
void back(int val,int p,int sumexp)
{
    if(p==nr+1)
    {
        if(sumexp&1) cnt-=1LL*(n/val)*(m/val);
        else cnt+=1LL*(n/val)*(m/val);
        return ;
    }
    back(val,p+1,sumexp);
    val=val*pr[p];
    if(val<0||val>mi) return ;
    back(val,p+1,sumexp+1);
}
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,0);
printf("%lld\n",cnt);
return 0;
}