Cod sursa(job #2636756)

Utilizator ElektrykT E S L A P E F E L I E Elektryk Data 19 iulie 2020 17:12:19
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in ("mins.in");
ofstream out ("mins.out");

const int LIM = 1e6 + 9;

int miu[LIM];

vector < int > primes;

int ciur[LIM];

int n, m;

long long ans;

int main()
{
    ciur[1] = 1;
    miu[1] = 1;
    for ( int i = 2 ; i < LIM ; ++i )
    {
        if ( ciur[i] == 0 )
        {
            primes.push_back (i);
            ciur[i] = i;
        }
        miu[i] = -miu[i / ciur[i]];
        if ( ciur[i] == ciur [i / ciur[i]] )
            miu[i] = 0;
        for ( int j = 0 ; j < primes.size ()  &&  i * primes[j] < LIM  &&  primes[j] <= ciur[i] ; ++j )
            ciur[i * primes[j]] = primes[j];
    }
    in >> n >> m;
    --n;
    --m;
    if ( n > m )
        swap ( n, m );
    for ( int i = 1 ; i <= n ; ++i )
        ans += 1LL * ( n / i ) * ( m / i ) * miu[i];
    out << ans;
    return 0;
}