Cod sursa(job #2636753)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 iulie 2020 16:57:49
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e6 + 5;

vector<int> primes;
int ciur[N], mu[N];

long long ans;
int n, m;

int main() {
	fi >> n >> m;
	--n, --m;
	if (n > m)
		swap(n, m);

	mu[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (ciur[i] == 0) {
			primes.push_back(i);
			ciur[i] = i;
		}
		mu[i] = -mu[i / ciur[i]];
		for (int j = 0; j < primes.size() && primes[j] <= ciur[i] && primes[j] * i <= n; ++j)
			ciur[primes[j] * i] = primes[j];
	}
	for (int i = 2; i * i <= n; ++i)
		mu[i * i] = 0;

	for (int i = 1; i <= n; ++i)
		ans+= 1LL * (n / i) * (m / i) * mu[i];
	
	fo << ans << '\n';

	return 0;
}