Pagini recente » infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #3038189) | Cod sursa (job #1772878) | Cod sursa (job #2294971) | Cod sursa (job #346197)
Cod sursa(job #346197)
#include <iostream>
using namespace std;
FILE *f = fopen("mins.in", "r"), *g = fopen("mins.out", "w");
int N, M, **a, *putere, *valori, *divz, nrDiv;
long total = 0;
int change(int &n, int &m)
{
int aux = n;
n = m;
m = aux;
return 0;
}
int preprocesare()
{
putere = new int[10];
putere[0] = 1;
for (int i = 1; i <= 9; ++i)
putere[i] = putere[i - 1] * 2;
a = new int* [128];
for (int i = 1; i < putere[7]; i++)
{
a[i] = new int[10];
int k = i, j = 0;
while (k)
{
a[i][++j] = k % 2;
k = k / 2;
}
a[i][0] = j;
}
return 0;
}
int main()
{
fscanf(f, "%d %d", &N, &M);
fclose(f);
if (N > M) change(N, M);
N--;M--;
//preprocesare
preprocesare();
valori = new int[N + 1];
divz = new int[10];
total = M;
for (int i = 2; i <= N; ++i)
{
for (int j = 1; j < 10; ++j)
divz[j] = 0;
nrDiv = 0;
int p = i, k = 2;
while (k < i / 2)
{
if (!(p % k))
{
divz[nrDiv++] = k;
while(!(p % k))
p = p / k;
}
k++;
}
if (!nrDiv)
divz[nrDiv++] = i;
int prod = 1;
for (int j = 0; j < nrDiv; ++j)
prod *= divz[j];
if (prod != i) {
total += valori[prod];
}
else
{
long totalIntermediar = M;
//fprintf(g, "%d\n", putere[nrDiv]);
for (int j = 1; j < putere[nrDiv]; ++j)
{
prod = 1;
int nrDe1 = 0;
//fprintf(g, "%d\n", a[j][0]);
for (int l = 1; l <= a[j][0]; ++l)
{
if (a[j][l])
{
//fprintf(g, "sadfsdfsd\n");
prod *= divz[l - 1];
nrDe1++;
}
}
//fprintf(g, "%d\n", prod);
if (!(nrDe1 % 2))
totalIntermediar += M / prod;
else
totalIntermediar = totalIntermediar - M / prod;
}
//fprintf(g, "%d\n", totalIntermediar);
total += totalIntermediar;
valori[i] = totalIntermediar;
}
}
fprintf(g, "%ld", total);
fclose(g);
return 0;
}