Cod sursa(job #2839851)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 26 ianuarie 2022 17:44:24
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>

int right;
int c[ 1000001 ];
bool ok[ 1000001 ];
void Eratostene() {
    for( int i = 2; i <= right; i++ )
        if( !c[ i ] ) {
            for( int j = i; j <= right; j += i )
                c[ j ]++;
            if( right / i >= i )
                for( int j = i * i; j <= right; j += i * i )
                    ok[ j ] = 1;
        }
}

int n, m;
int op[] = { 1, -1 };
int main()
{
    FILE *fin = fopen( "mins.in", "r" );
    fscanf( fin, "%d %d", &n, &m );
    fclose( fin );

    --n, --m;
    right = ( n <= m ? n : m );
    {Eratostene();}

    long long sol = ( long long )n * m;
    for( int i = 2; i <= right; i++ )
        if( !ok[ i ] )
            sol += op[ c[ i ] & 1 ] * ( long long )( n / i ) * ( m / i );
    FILE *fout = fopen( "mins.out", "w" );
    fprintf( fout, "%lld\n", sol );
    fclose( fout );    
    return 0;
}