Cod sursa(job #2636771)

Utilizator game_difficultyCalin Crangus game_difficulty Data 19 iulie 2020 20:11:03
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <cmath>

using namespace std;

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

int miu[1000005];
void precalc() {
	miu[1] = 1;
	for (int i = 2; i <= 1000000; i++) {
		if (miu[i] == 0) {
			for (int j = i; j <= 1000000; j += i)
				miu[j]++;
		}
		if (miu[i] % 2 == 0)
			miu[i] = 1;
		else
			miu[i] = -1;
	}
	for (int i = 4; i <= 1000000; i++) {
		if (int(sqrt(i)) == sqrt(i)) {
			for (int j = i; j <= 1000000; j += i) {
				miu[j] = 0;
			}
		}
	}
}

int main() {
	precalc();
	int n, m;
	long long s = 0;
	in >> n >> m;
	n--;
	m--;
	for (int i = 1; i <= n; i++) {
		s += 1LL * (n / i) * (m / i) * miu[i];
	}
	out << s;
	return 0;
}

/*
n - n / 2 - n / 3 - n / 5 + n / 6 + n / 10 + n / 15 - n / 30
*/