Cod sursa(job #2952696)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 9 decembrie 2022 18:59:12
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>

using namespace std;

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

const int DIM = 1000001;
long long c, d, minn, sol;
int divCnt[DIM];
bool f[DIM], g[DIM];

int main() {
    fin >> c >> d;

    c--, d--;
    minn = min(c, d);
    sol = 1LL * c * d;
    for (int i = 2; i <= minn; i++) {
        if (!f[i]) {
            for (int j = 2 * i; j <= minn; j += i) {
                f[j] = true;
                if (j % (i * i) == 0)
                    g[j] = true;
                divCnt[j]++;
            }
            divCnt[i] = 1;
        }

        if (!g[i]) {
            long long val = 1LL * (c / i) * (d / i);
            if (divCnt[i] % 2 == 0)  sol += val;
            else                     sol -= val;

        }
    }

    fout << sol;

    return 0;
}