Cod sursa(job #3311284)

Utilizator razvanmrt_06Mariuta Razvan razvanmrt_06 Data 20 septembrie 2025 22:42:09
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>

using namespace std;

const int Cmax = 1000005;

int c, d, ciur[Cmax], antiSol;
bool bad[Cmax];

int findCoef(int nr){
    if(bad[nr]){
        return 0;
    }
    if(ciur[nr] % 2 == 0){
        return -1;
    }
    return 1;
}

int main(){
    ifstream fin("mins.in");
    ofstream fout("mins.out");
    fin >> c >> d;
    c--; d--;

    // cautam perechile (x,y) cu 1 <= x <= c && 1 <= y <= d
    // astfel incat cmmdc(x, y) >= 2

    for(int i = 2; i <= min(c,d); i++){
        ciur[i] = 1;
    }
    for(int i = 2; i * i <= min(c,d); i++){
        if(ciur[i]){
            for(int j = 2 * i; j <= min(c,d); j += i){
                ciur[j]++;
            }
            for(int j = i * i; j <= min(c,d); j += i*i){
                bad[j]=true;
            }
        }
    }

    for(int k = 2; k <= min(c,d); k++){
        int aux = (c/k)*(d/k);
        int coef = findCoef(k);
        antiSol = antiSol + coef*aux;
    }
    
    fout << c*d - antiSol;

    return 0;
}