Cod sursa(job #1982497)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 18 mai 2017 23:21:17
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>

using namespace std;

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

const int nmax = 1e6;

int o[nmax + 1];
bool ciur[nmax + 1], najp[nmax + 1];

int main() {
    int c, d;

    fin >> c >> d;
    -- c, -- d;

    long long ans = 1LL * c * d;

    int lim = min(c, d);

    for (int i = 2; i <= lim; ++ i) {
        if (ciur[ i ] == 0) {
            for (long long j = 1LL * i * i; j <= lim; j += 1LL * i * i) {
                najp[ j ] = 1;
            }
            for (int j = i; j <= lim; j += i) {
                ++ o[ j ]; ciur[ j ] = 1;
            }
        }
    }

    for (int i = 2; i <= lim; ++ i) {
        if (najp[ i ] == 0) {
            if (o[ i ] % 2) ans -= 1LL * (c / i) * (d / i);
            else            ans += 1LL * (c / i) * (d / i);
        }
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}