Cod sursa(job #2637011)

Utilizator betybety bety bety Data 20 iulie 2020 21:48:28
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("mins.in");
ofstream out ("mins.out");
const int LIM = 1e6 + 9;
vector < int > primes;
int miu[LIM],ciur[LIM], 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;
}