Cod sursa(job #592267)

Utilizator darrenRares Buhai darren Data 27 mai 2011 15:13:39
Problema Mins Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N, M;
int phi[1000002];
long long total;

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

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

    if (N < M) swap(N, M);

    for (int i = 1; i <= N; ++i)
        phi[i] = i;
    for (int i = 2; i <= N; ++i)
        if (phi[i] == i)
            for (int j = i; j <= N; j += i)
                phi[j] -= phi[j] / i;

    for (int i = 1; i <= N; ++i)
        total += (long long) phi[i];
    total *= 2LL, --total;

    for (int i = M + 1; i <= N; ++i)
        total -= (long long) phi[i];

    fout << total;

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