Cod sursa(job #1456759)

Utilizator cojocarugabiReality cojocarugabi Data 1 iulie 2015 20:19:01
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
# include <bits/stdc++.h>
# define ll long long
using namespace std;
ifstream fi("mins.in");
ofstream fo("mins.out");
const int nmax = 1e6 + 55;
bitset < nmax > b;
int d[nmax];
int main(void)
{
    ll n,m;
    fi>>n>>m;
    --n;--m;
    ll ans = n * m;
    ll mx = max(n,m);
    for (int i = 2;i <= mx;++i)
    if (!d[i])
    {
        d[i] = 1;
        for (int j = 2*i;j <= mx;j += i) ++d[j];
    }
    for (int i = 2;i <= mx;++i) b[i] = 1;
    for (int i = 2;i*i <= mx;++i)
        if (d[i] == 1)
            for (int j = i*i;j <= mx;j += i*i) b[j] = 0;
    for (int i = 2;i <= mx;++i)
      if (b[i])
        ans -= 1ll * (d[i]&1 ? 1:-1) * (n / i) * (m / i);
    return fo << ans << '\n',0;
}