Cod sursa(job #1323173)

Utilizator felixiPuscasu Felix felixi Data 20 ianuarie 2015 19:34:31
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>

using namespace std;

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

typedef long long I64;

const int N = 1e6 + 5;

int n, m, d[N];
I64 sol, M;
bool no[N];

int main()
{
    in >> m >> n;
    m--, n--;
    sol = 1LL * m * n;
    M = max(m, n);
    for (I64 i = 2; i <= M; ++i)
    {
        if (d[i])
            continue;
        d[i] = 1;
        for (int j = i * 2; j <= M; j += i)
            d[j]++;
        for (I64 j = i * i; j <= M; j += i * i)
            no[j] = 1;
    }
    for (int i = 2; i <= M; ++i)
        if (!no[i])
            sol -= 1LL * (d[i] % 2 ? 1 : -1) * (m / i) * (n / i);
    out << sol << '\n';
}