Cod sursa(job #3311285)

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

using namespace std;

const int Cmax = 1000005;

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

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++){
        long long aux = (c/k)*(d/k);
        if(bad[k]){
            continue;
        }
        if(ciur[k] % 2 == 1){
            antiSol += aux;
        }
        else{
            antiSol -= aux;
        }
    }
    
    fout << c*d - antiSol;

    return 0;
}