Cod sursa(job #2034688)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 8 octombrie 2017 12:23:13
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

#define ll long long
#define Cmax 1000005
#define inf 1000000000

using namespace std;

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

int C, D;
ll S;
int c[Cmax];
int ok[Cmax];

int main()
{
    fin >> C >> D;
    C--, D--;
    S = 1ll * C * D;
    for(int i = 2; i <= min(C, D); i++)
        c[i] = 1, ok[i] = inf;
    for(int i = 2; i * i <= min(C, D); i++)
        if(c[i])
        for(int j = i * i; j <= min(C, D); j += i)
            c[j] = 0;
    for(int i = 2; i <= min(C, D); i++)
        if(c[i])
        for(int j = min(C, D) / i; j >= 1; j--)
            if(ok[j] != inf)
                ok[j * i] = 1 + ok[j];
    for(int i = 2; i <= min(C, D); i++)
        if(ok[i] != inf)
        if(ok[i] % 2 == 1)
            S -= 1ll * (C / i) * (D / i);
        else
            S += 1ll * (C / i) * (D / i);
    fout << S << "\n";
    return 0;
}