Pagini recente » Cod sursa (job #658532) | Cod sursa (job #1791940) | Profil tudorgalatan | Diferente pentru utilizator/eugenstoica intre reviziile 19 si 39 | Cod sursa (job #3125945)
#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]
**/