Cod sursa(job #342714)

Utilizator alex23alexandru andronache alex23 Data 23 august 2009 09:45:54
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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, *mVect;

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);

	a = new int[n];
	mVect = new int[m];
	divz = new int[20];
	
	for (int i = 1; i < m; ++i)
	{
		mVect[i] = 0;
	}
	
	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 / 2)
		{
			if (!(k % p))
			{
				divz[nr++] = p;
				while (!(k % p))
				{
					k = k / p;
				}
			}
			++p;
		}
		if ((i != 1) && (nr == 0))
			divz[nr++] = i;
		
		int prod = 1;
		for (int j = 0; j < nr; ++j)
			prod *= divz[j];
			
		if ((prod != i) && (i > 1))
		{
			total += mVect[prod];
		}
		else
		{
			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);
			mVect[i] = n - s - 1;
		}
	}

	delete[] a;
	delete[] divz;

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