Cod sursa(job #2163334)

Utilizator giotoPopescu Ioan gioto Data 12 martie 2018 17:48:21
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m;
int nr[1000005];
bool f[1000005];
int main()
{
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    --n; --m;
    for(int i = 2; i <= n ; ++i){
        if(nr[i]) continue ;
        for(int j = i; j <= n ; j += i)
            ++nr[j];
        if(n / i < i) continue ;
        for(int j = i * i; j <= n ; j += i * i)
            f[j] = 1;
    }
    long long Sol = 1LL * n * m;
    for(int i = 2; i <= n ; ++i){
        if(f[i]) continue ;
        if(nr[i] % 2 == 0) Sol = Sol + 1LL * (n / i) * (m / i);
        else Sol = Sol - 1LL * (n / i) * (m / i);
    }
    printf("%lld", Sol);
    return 0;
}