Cod sursa(job #1251975)

Utilizator felixiPuscasu Felix felixi Data 30 octombrie 2014 09:31:58
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <cmath>

using namespace std;

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

const int NMAX = 1000000;
const int PMAX = 1000;

bool ciur[PMAX+2];
int pr[PMAX+1], pr_ind= 0;

void ciurul() {                       ///  Ciurul pana la 1000(Y_MAX=1000000)... Ce mai ramane din Y e PRIM
    int lim= (int)sqrt( 1.0*PMAX );
    for( int i= 2;  i<=lim;  ++i ) {
        if( !ciur[i] ) {
            pr[ ++pr_ind ]= i;
            for( int j= i*i;  j<=PMAX;  j+=i )  ciur[j]= 1;
        }
    }
    for( int i= lim+1;  i<=PMAX;  ++i ) {
        if( !ciur[i] )  pr[ ++pr_ind ]= i;
    }
}

int PINEX( int X, int Y ) {   ///  Cate numere <= X sunt prime cu Y
    if( Y==1 ) return X;    ///   Toate numerele mai mici sau egale cu X sunt prime cu 1
    int p[PMAX+1], R= 0, ind= 1, lim= (int)sqrt(1.0*Y);
    ///  Descompun in factori primi
    while( Y>1 && pr[ind]<=lim ) {
        int cnt= 0;
        while( Y%pr[ind] == 0 ) {
            ++cnt;
            Y/= pr[ind];
        }
        if( cnt ) {
            p[ ++R ]= pr[ind];
            lim= (int)sqrt(1.0*Y);
        }
        ++ind;
    }
    if( Y>1 ) p[ ++R ]= Y;
    ///  PINEX  :))
    int sol= 0, k=(1<<R);
    for( int i= 1;   i<k;  ++i ) {
        int cnt= 0, prod= 1;
        for( int j= 0;  j<R;  ++j ) {
            if( i&(1<<j) ) {
                ++cnt;
                prod*= p[j+1];
            }
        }
        if( cnt%2 == 1 )  sol+= X/prod;
        else              sol-= X/prod;
    }
    ///    Raspunsul
    return X-sol;
}

int main() {
    ciurul();
    int rasp= 0;
    int N,M;
    in >> N >> M;   --N;  --M;
    if( N > M )  swap(N,M);
    for( int i= 1;  i<=N;  ++i ) {
        rasp+= PINEX( M, i );
    }
    out << rasp << '\n';
    return 0;
}