Cod sursa(job #547480)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 6 martie 2011 13:16:59
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>

#define minim(a,b) (a<b ? a : b)
#define maxim(a,b) (a>b ? a : b)
#define ll long long
#define NMAX 1000005

char prim[NMAX],grad[NMAX];
char ok[NMAX];
ll r,sol;
int m,n;

int main ()
{
    int i,j,cn,cm,ci;
    
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    scanf("%d%d",&n,&m);
    cn=minim(n,m);
    cm=maxim(n,m);
    n=cn;m=cm;
    n--;
    m--;
    for(i=2;i<=n;i++)
        if(!prim[i])
        {
            for(j=i+i;j<=n;j+=i)
            {
                prim[j]=1;
                grad[j]++;
            }
            grad[i]=1;
            if((ll)i*i>n)
                continue;
            ci=i*i;
            for(j=ci;j<=n;j+=ci)
                ok[j]=1;
        }
    for(i=2;i<=n;i++)
    {
        if(ok[i])
            continue;
        r=m/i;
        if(!(grad[i]&1))
            r=-r;
        sol+=r*(n/i);
    }
    printf("%lld\n",(ll)m*n-sol);
    return 0;
}