Cod sursa(job #1698505)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 mai 2016 17:04:30
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

const int DIM = 1 << 20;
using namespace std;

int Dp[DIM], Ok[DIM], C, D, val; long long answer;

int main() {

    FILE *input_file  = fopen( "mins.in" , "r" );
    FILE *output_file = fopen( "mins.out", "w" );

    fscanf( input_file, "%d %d", &C, &D );
    if( C > D ) swap( C, D ); C --; D --;

    answer = 1LL * C * D;
    for( int i = 2; i <= C; i ++ ) {
        if( Dp[i] == 0 ) {
            if( 1LL * i * i <= C )
                val = i * i;
            else
                val = C + 1;

            for( int j = i; j <= C; j += i ) {
                Dp[j] ++;

                if( j % val == 0 )
                    Ok[j] = 1;
            }
        }

        if( Ok[i] == 1 )
            continue;

        if( Dp[i] % 2 == 1 )
            answer -= 1LL * (C / i) * (D / i);
        else
            answer += 1LL * (C / i) * (D / i);
    }

    fprintf( output_file, "%lld\n", answer );

    return 0;
}