Cod sursa(job #3125945)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 4 mai 2023 20:28:16
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("mins.in");
ofstream out("mins.out");

const int VMAX = 1000000;
int n,m;
int mobius[1000005];
bool sieve[1000005];
vector<int>primes;

void prec()
{
    for (int i = 1; i <= VMAX; i++)
        mobius[i] = 1;
    for (int i = 2; i * i <= VMAX; i++)
        if (!sieve[i])
            for (int j = i * i; j <= VMAX; j += i)
                sieve[j] = true;
    for (int i = 2; i <= VMAX; i++)
        if (!sieve[i])
            primes.push_back(i);
    for (int i = 0; i < primes.size(); i++)
        for (int j = primes[i]; j <= VMAX; j += primes[i])
            mobius[j] = -mobius[j];
    for (int i = 0; primes[i] * primes[i] <= VMAX; i++)
        for (int j = primes[i] * primes[i]; j <= VMAX; j += primes[i] * primes[i])
            mobius[j] = 0;
}

int main()
{
    prec();
    in >> n >> m;
    n--,m--;
    long long gd = 0;
    for (int i = 1; i <= min(n,m); i++)
        gd += 1ll * (n / i) * (m / i) * mobius[i];
    out << gd;
    return 0;
}

/**
raspunsul este nr de fractii ired cu 1 <= a <= n si 1 <= b <= m
nr fractii neired = sum((n / i) * (m / i)) * mobius[i]
**/