Cod sursa(job #2502229)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 30 noiembrie 2019 15:07:30
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>

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