Cod sursa(job #951102)

Utilizator matei_cChristescu Matei matei_c Data 19 mai 2013 12:09:07
Problema Pairs Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<algorithm>
using namespace std ;

ifstream fin("mins.in");
ofstream fout("mins.out");

#define maxn 1000001
#define inf 100000000

int n, m ;

int nr[maxn] ;

long long sol ;

int main ()
{
    fin >> n >> m ;

    --n ;
    --m ;

    int lim = min( n, m ) ;

    for(int i = 2; i <= lim; ++i )
    {
        if ( nr[i] == 0 )
        {
            for(long long j = ( long long ) i * i; j <= lim; j += ( long long ) i * i )
                nr[j] = -inf ;

            for(int j = i; j <= lim; j += i )
                ++nr[j] ;
        }
    }

    for(int i = 1; i <= lim; ++i )
    {
        if( nr[i] > 0 )
        {
            if( nr[i] % 2 == 1 )
                sol -= ( long long ) ( n / i ) * ( m / i ) ;
            else
                sol += ( long long ) ( n / i ) * ( m / i ) ;
        }
    }

    sol += ( long long ) n * m ;

    fout << sol ;

    return 0 ;
}