Cod sursa(job #925950)

Utilizator cruceruvladCruceru Vlad cruceruvlad Data 24 martie 2013 20:41:28
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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 / 2)
        {
            if (!(k % p))
            {
                divz[nr++] = p;
                while (!(k % p))
                {
                    k = k / p;
                }
            }
            ++p;
        }
        if ((i != 1) && (nr == 0))
            divz[nr++] = i;
        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;
}