Pagini recente » Cod sursa (job #3190314) | Profil LilianaL | Profil andrici_cezar | Profil Fetita_Jucausa | Cod sursa (job #342714)
Cod sursa(job #342714)
#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;
}