Cod sursa(job #1370455)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 3 martie 2015 14:47:59
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 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;

    fill(valid + 2, valid + L + 1, true);

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

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

        for (long long j = 1LL * i * i; j <= L; j += 1LL * i * i )
            valid[j] = false;

        if ( sieve[i] & 1 )
            sol -= 1LL * (C / i) * (D / i);
        else
            sol += 1LL * (C / i) * (D / i);
    }

    out << sol << "\n";

    return 0;
}