Cod sursa(job #455906)

Utilizator SpiderManSimoiu Robert SpiderMan Data 14 mai 2010 15:40:04
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

const int N_MAX = 500005;
const char FIN[] = "mins.in";
const char FOU[] = "mins.out";

int sol[N_MAX][15], AUX[N_MAX], V[N_MAX];
int x2, y2, ct;

int euler( int n )
{
    int p = n;
    for (int i = 1; i <= AUX[n]; ++i)
       p = ( p / sol[n][i] ) * ( sol[n][i] - 1 );
    return p;
}

int ggt1( int n1, int n2 )
{
    for (int j = 1; j <= AUX[n2]; ++j)
       if ( n1 % sol[n2][j] == 0 ) return 2;
    return 1;
}

int main()
{
    freopen(FIN , "r" , stdin);
    freopen(FOU , "w" , stdout);

    scanf("%d %d", &x2, &y2);

    int dx = x2 - 1;
    int dy = y2 - 1;
    int mini, maxi;

    if ( dx < dy ) mini = dx, maxi = dy;
    else mini = dy, maxi = dx;

    AUX[1] = sol[1][1] = 1;

    for (int i = 2; i <= mini; ++i)
       if ( V[i] == 0 )
         for ( int j = i; j <= mini; j += i )
            sol[j][++AUX[j]] = i, V[j] = 1;

    for (int i = 2; i <= mini; ++i)
        ct += euler(i);

    ct <<= 1, ct += maxi, ct -= mini;

    for (int i = mini + 1; i <= maxi; ++i)
      for (int j = 2; j <= mini; ++j)
         if ( ggt1(i, j) == 1 ) ct++;

    printf("%d", ++ct);

    return 0;
}