Cod sursa(job #1744303)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 19 august 2016 16:20:18
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>
using namespace std;
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)
        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 -= (n / i) * (m / i);
            else
                x += (n / i) * (m / i);
        }
    }
    printf("%lld", x);
    return 0;
}