Cod sursa(job #1409410)

Utilizator vazanIonescu Victor Razvan vazan Data 30 martie 2015 15:17:16
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1000000;

int sieve[Nmax + 1];
bool valid[Nmax + 1];
int C, D;

int main()
{
    ifstream in("mins.in");
    ofstream out("mins.out");

    in >> C >> D;
    C--; D--;

    int L = min(C, D);
    long long sol = 1LL * C * D;

    for ( int i = 2; i <= L; ++i )
    {
        if ( sieve[i] ) continue;

        for ( int j = i; j <= L; j += i )
            sieve[j]++;

        if ( 1LL * i * i <= L )
            for (int j = i * i; j <= L; j += i * i )
                valid[j] = true;
    }

    for ( int i = 2; i <= L; ++i )
        if ( valid[i] == false )
        {
            if ( sieve[i] & 1 )
                sol -= 1LL * (C / i) * (D / i);
            else
                sol += 1LL * (C / i) * (D / i);
        }

    out << sol << "\n";

    return 0;
}