Cod sursa(job #928240)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 26 martie 2013 12:51:30
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, v[1000010], i, j, t, aux;
long long a;
int main(){
    freopen("mins.in", "r", stdin);
    freopen("mins.out","w", stdout);
    scanf("%d %d", &n, &m);
    t=min(n, m)-1;
    for(i=2; i<=t; i++)
    {
        if(!v[i])
        {
            for(j=i; j<=t; j+=i)
                v[j]++;
            if(i<=t/i)
            {
                aux=i*i;
                for(j=aux; j<=t; j+=aux)
                    v[j]=-10000000;
            }
        }
        if(v[i]>=0)
        {
            if(v[i] & 1)
                a-=(long long)( (n-1)/i )*( (m-1)/i );
            else
                a+=(long long)( (n-1)/i )*( (m-1)/i );
        }
    }
    printf("%lld\n", a+(long long)(n-1)*(m-1));
    return 0;
}