Cod sursa(job #3311291)

Utilizator razvanmrt_06Mariuta Razvan razvanmrt_06 Data 20 septembrie 2025 23:22:48
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#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--;
    int n = min(c,d);

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

    for (int i = 2; i <= n; i++)
    {
        if (ciur[i] == 0)
        {
            for (int j = i; j <= n; j += i)
            {
                ciur[j]++;
            }
            long long k = 1LL * i * i;
            for(long long j = k; j <= n; j += k){
                bad[j] = 1;
            }
        }
    }

    for (int k = 2; k <= n; k++)
    {
        if(!bad[k]){
            long long aux = 1LL * (c / k) * (d / k);
            if (ciur[k] % 2 == 1)
            {
                antiSol += aux;
            }
            else
            {
                antiSol -= aux;
            }
        }
    }
    fout << 1LL * c*d - antiSol;

    return 0;
}