Cod sursa(job #2952692)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 9 decembrie 2022 18:56:15
Problema Mins Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 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;
                g[j] = !(j % (i * i));
                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;
}