Cod sursa(job #2836500)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 20 ianuarie 2022 15:35:32
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

int cmmdc(int x,int y) {
	if(!y) return x;
	return cmmdc(y,x%y);
}

int main() {
	ifstream cin("mins.in");
	ofstream cout("mins.out");
	int c, d;
	cin >> c >> d;
	c--, d--;
	int ans = c * d;
	int hmin = min(c,d);
	vector<int> div(hmin+1, 0); // numarul de divizori
	vector<bool> mul(hmin+1, 0); // verificam daca este multiplu de patrat perfect
	for(int i = 2; i <= hmin; i++) {
		if(!div[i]) {
			for(int j = i; j <= hmin; j += i)
				div[j]++;
			for(int j = i*i; j <= hmin; j += i*i )
				mul[j] = 1;
		}
		if(!mul[i]) {
			int aux = (c/i) * (d/i);
			if(div[i]%2 == 0) ans += aux;
			else ans -= aux;
		}
	}
	cout << ans << '\n';
	
	
	return 0;
}