Cod sursa(job #346197)

Utilizator alex23alexandru andronache alex23 Data 7 septembrie 2009 09:37:02
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#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;
}