Cod sursa(job #2701149)

Utilizator AlexDontuAlex Dontu AlexDontu Data 29 ianuarie 2021 22:46:09
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("mins.in");
ofstream g ("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];
}
f >> 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];
g << ans;
return 0;
}