Cod sursa(job #2636612)

Utilizator game_difficultyCalin Crangus game_difficulty Data 18 iulie 2020 20:24:11
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>

using namespace std;

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

int l[1000001], w[1000001];
vector<int> prime;
int c, d;

void do_p() {
	for (int i = 2; i <= 1000000; i++) {
		if (l[i] == 0) {
			l[i] = i;
			prime.push_back(i);
			w[i] = prime.size() - 1;
		}
		for (int j = w[l[i]]; j >= 0 && 1ll * i * prime[j] <= 1000000; j--) {
			l[i * prime[j]] = prime[j];
		}
	}
}

bool coprime(int a, int b) {
	if (a == 1 || b == 1)
		return 1;
	while (l[a] != l[b] && a > 1 && b > 1) {
		if (l[a] > l[b])
			b /= l[b];
		else
			a /= l[a];
	}
	if (l[a] == l[b])
		return 0;
	return 1;
}

int phi_p(int x) {
	if (x <= d)
		return x - 1;
	return d;

}

int phi(int x) {
	int p = 1;
	while (x > 1) {
		p *= phi_p(l[x]);
		x /= l[x];
	}
	return p;
}

int phi_no_res(int x) {
	int p = 1;
	while (x > 1) {
		p *= l[x] - 1;
		x /= l[x];
	}
	return p;
}

int main() {
	do_p();
	int ans = 0;
	in >> c >> d;
	if (c < d)
		swap(c, d);
	for (int i = 1; i <= c - 1; i++) {
		ans += phi(i);
	}
	for (int i = 1; i <= d - 1; i++) {
		ans += phi_no_res(i);
	}
	out << ans;
	return 0;
}