Cod sursa(job #592833)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 30 mai 2011 20:57:50
Problema Mins Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
# include <fstream>
using namespace std;

int i, j, c, d, phi1[200100], phi2[200100];
long long sol;
int main ()
{
	ifstream f ("mins.in");
	ofstream g ("mins.out");
	
	f >> c >> d;
	--c, --d;
	
	if (c > d) c ^= d ^= c ^= d;
	// c < d
	
	// pentru c
	for (i = 1; i <= c; ++i)
		phi1[i] = i - 1;
	for (i = 2; i <= c; ++i)
		if (phi1[i] == i - 1)
			for (j = i; j <= d; j += i)
				phi1[j] -= phi1[j] / i;
	
	// pentru d
	for (i = 1; i <= d; ++i)
		phi2[i] = i - 1;
	for (i = 2; i <= d; ++i)
		if (phi2[i] == i - 1)
			for (j = i; j <= c; j += i)
				phi2[j] -= phi2[j] / i;
	
	for (i = 1; i <= c; ++i)
		sol = (long long)(sol + phi1[i]);
	for (i = 1; i <= d; ++i)
		sol = (long long)(sol + phi2[i]);
	
	g << sol + 1 << '\n';
	
	g.close ();
	return 0;
}