Cod sursa(job #961359)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 22:25:25
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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 ;
}