Cod sursa(job #2836505)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 20 ianuarie 2022 15:47:40
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 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--;
	long long ans = 1LL*c * d;
	int hmin = min(c,d);
	vector<int> div(hmin+2, 0); // numarul de divizori
	vector<bool> mul(hmin+2, 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(long long j = 1LL*i*i; j <= hmin; j += 1LL*i*i )
				mul[j] = 1;
		}
		if(!mul[i]) {
			long long aux = 1LL * (c/i) * (d/i);
			if(div[i]%2 == 0) ans += aux;
			else ans -= aux;
		}
	}
	cout << ans << '\n';
	
	
	return 0;
}