Cod sursa(job #2938830)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 12 noiembrie 2022 17:19:18
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

const int VMAX = 1e6;

int mob[VMAX + 1];

void buildMob(int n) {
	mob[0] = mob[1] = 1;
	for(int i = 2; i <= n; i++) {
		if(mob[i] == 0) { // i este prim
			mob[i] = -1;

			for(int j = i + i; j <= n; j += i) {
				if(mob[j] == 0) {
					mob[j] = -1;
				} else {
					mob[j] = -mob[j];
				}
			}
		}
	}

	for(int i = 2; i * i <= n; i++) {
		mob[i * i] = 0;
	}

	for(int i = 2; i <= n; i++) {
		if(mob[i] == 0) {
			for(int j = i + i; j <= n; j += i) {
				mob[j] = 0;
			}
		}
	}
}

int main() {
	int c, d;
	fin >> c >> d;

	if(c < d) {
		swap(c, d);
	}

	buildMob(VMAX);

	long long ans = 0;

	for(int i = 1; i < d; i++) {
		ans += mob[i] * ((long long) (c - 1) / i) * ((long long) (d - 1) / i);
	}

	fout << ans << '\n';
	return 0;
}