Cod sursa(job #342513)

Utilizator alex23alexandru andronache alex23 Data 22 august 2009 09:17:13
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>


using namespace std;

FILE *f = fopen("mins.in", "r"), *g = fopen("mins.out", "w");
long total = 0;
int n, m;
int *a, *divz;

int cmmdc(int a, int b)
{
	int x;
	if (a < b) {x = a;a = b;b = x;}
    while (b)
       {x = b;
        b = a % b;
        a = x;
        }
    x = a;
	return x;
}


int main() 
{
	fscanf(f, "%d %d", &n, &m);
	fclose(f);

	//cout << n << " " << m << endl;
	a = new int[n];
	divz = new int[20];
	for (int i = 1; i < m; ++i)
	{
		for (int j = 1; j < n; ++j)
		{
			a[j] = 0;
		}
		int k = i, p = 2, nr = 0;
		while (p <= i)
		{
			if (!(k % p))
			{
				divz[nr++] = p;
				while (!(k % p))
				{
					k = k / p;
				}
			}
			++p;
		}
		for (int j = 0; j < nr; ++j)
			for (int k = divz[j]; k < n; k += divz[j])
				a[k] = 1;
		int s = 0;
		for (int j = 1; j < n; ++j)
		{
			s += a[j];
		}
		//cout << s << endl;
		total += (n - s - 1);
	}

	delete[] a;
	delete[] divz;

	fprintf(g, "%ld", total);
	fclose(g);
	return 0;
}