Cod sursa(job #592987)

Utilizator darrenRares Buhai darren Data 31 mai 2011 19:11:20
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>

using namespace std;

typedef long long i64;

int N, M;
long long total;
int prim[1000002];
bool cannot[1000002];

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

    fin >> N >> M;
    --N, --M;

    total = (i64) N * M;
    for (i64 i = 2; i <= 1000000; ++i)
    {
        if (prim[i]) continue;

        prim[i] = 1;
        for (i64 j = 2 * i; j <= 1000000; j += i) // marchez cati divizori primi are fiecare numar
            ++prim[j];
        for (i64 j = i * i; j <= 1000000; j += i * i) // sar peste numerele care au in descompunere factori primi la putere mai mare decat 1
            cannot[j] = true;
    }

    for (i64 i = 2; i <= 1000000; ++i)
        if (!cannot[i])
            total -= (prim[i] % 2 == 0 ? -1 : 1) * (i64) (N / i) * (M / i);

    fout << total;

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