Cod sursa(job #2883622)

Utilizator LuciBBadea Lucian LuciB Data 1 aprilie 2022 17:33:30
Problema Mins Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
const int VALMAX = 1e6;

int nrdiv[VALMAX + 1];
int prime[VALMAX];

int main() {
    int n, x, y, nrprime;
    FILE *fin, *fout;

    fin = fopen("mins.in", "r");
    fscanf(fin, "%d%d", &x, &y);
    fclose(fin);

    n = min(x - 1, y - 1);
    nrprime = 0;
    for(int i = 2; i <= n; i++) {
        if(nrdiv[i] == 0) {
            prime[nrprime++] = i;
            for(int d = i; d <= n; d += i)
                nrdiv[d]++;
        }
    }
    int i = 0;
    while(i < nrprime && prime[i] * prime[i] <= n) {
        for(int d = prime[i] * prime[i]; d <= n; d += prime[i] * prime[i])
            nrdiv[d] = -1;
        i++;
    }
    long long ans = 1LL * (x - 1) * (y - 1);
    for(int i = 2; i <= n; i++) {
        if(nrdiv[i] != -1) {
            if(nrdiv[i] % 2 == 0)
                ans += (1LL * (x - 1) / i) * (1LL * (y - 1) / i);
            else
                ans -= (1LL * (x - 1) / i) * (1LL * (y - 1) / i);
        }
    }
    
    fout = fopen("mins.out", "w");
    fprintf(fout, "%lld", ans);
    fclose(fout);

    return 0;
}