Cod sursa(job #1418369)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 12 aprilie 2015 21:11:16
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#define N 1e6+5
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
int n, m, d[N];
long long sol, M;
bool nok[N];
int main()
{
    f>>m>>n;
    m--;
    n--;
    sol = 1LL * m * n;
    M =max(m, n);
    for (long long i = 2; i <= M; ++i)
    {
        if (d[i])
            continue;
        d[i] = 1;
        for (int j = i * 2; j <= M; j += i)
            d[j]++;
        for (long long j = i * i; j <= M; j += i * i)
            nok[j] = 1;
    }
    for (int i = 2; i <= M; ++i)
        if (!nok[i])
            sol -= 1LL * (d[i] % 2 ? 1 : -1) * (m / i) * (n / i);
    g << sol;
}