Cod sursa(job #2675480)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 21 noiembrie 2020 20:27:19
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <iostream>
using namespace std;

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

using i64 = long long;

const int N = 1e6 + 6;

int mu[N];

int main() {
	i64 ant = 0;
	int n, m;

	fi >> n >> m;
	--n, --m;
	for (int i = 2; i <= n; ++i) if (mu[i] == 0) {
		for (int j = i; j <= n; j+= i)
			++mu[j];
	}

	for (int i = 1; i <= n; ++i)
		mu[i] = (mu[i] % 2 == 0 ? 1 : -1);

	for (int i = 2; i * i <= n; ++i)
		for (int j = i * i; j <= n; j+= i * i)
			mu[j] = 0;

	for (int i = 1; i <= n; ++i)
		ant+= mu[i] * (m / i);
	

	fo << 1LL * n * m - ant << endl;

	return 0;
}