Cod sursa(job #2952751)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 9 decembrie 2022 20:51:46
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>

#define DIM 1000010
using namespace std;
int c, d, n, nrd[DIM];
long long nr, x;
bool f[DIM], ok[DIM];

int main() {
    ifstream fin("mins.in");
    ofstream fout("mins.out");
    fin >> c >> d;
    c--;
    d--;
    n = min(c, d);
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            for (int j = i + i; j <= n; j += i) {
                f[j] = true;
                nrd[j]++;
                if (j % (i * i) == 0) {
                    ok[j] = true;
                }
            }
            nrd[i] = 1;
        }
        if (!ok[i]) {
            x = 1LL * (c / i) * (d / i);
            if (nrd[i] % 2 == 1) {
                nr += x;
            } else {
                nr -= x;
            }
        }
    }
    nr = 1LL * c * d - nr;
    fout << nr << "\n";
    return 0;
}