Cod sursa(job #1612678)

Utilizator Athena99Anghel Anca Athena99 Data 24 februarie 2016 23:19:42
Problema Mins Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>

using namespace std;

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

typedef long long i64;

const i64 nmax= 1000000;

i64 d[nmax+1], p[nmax+1];

int main(  ) {
    i64 n, m;
    fin>>n>>m;
    --n, --m;
    for ( i64 i= 2; i<=max(n, m); ++i ) {
        if ( d[i]==0 ) {
            d[i]= 1;
            for ( i64 j= i*2; j<=max(n, m); j+= i ) {
                ++d[j];
            }
            for ( i64 j= i*i; j<=max(n, m); j+= (i64)i*i ) {
                p[j]= 1;
            }
        }
    }

    i64 sol= (i64)n*m;
    for ( i64 i= 2; i<=max(n, m); ++i ) {
        if ( p[i]==0 ) {
            i64 sign= 1;
            if ( d[i]%2==1 ) {
                sign= -1;
            }

            sol= (i64)sol+(i64)(n/i)*(m/i)*sign;
        }
    }

    fout<<sol<<"\n";

    return 0;
}