Cod sursa(job #1694519)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 aprilie 2016 15:58:32
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 1000505;
int N, M, cntPrimeFactors[NMAX];
bool hasSquareFactor[NMAX];

int main() {
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);

    scanf("%d%d", &N, &M);
    N--; M--;
    if (N > M) {
        swap(N, M);
    }

    for (int i = 2; i <= N; i++) {
        if (!cntPrimeFactors[i]) {
            cntPrimeFactors[i] = 1;
            for (int j = 2 * i; j <= N; j += i) {
                cntPrimeFactors[j]++;
                if (j % (1LL * i * i) == 0) {
                    hasSquareFactor[j] = true;
                }
            }
        }
    }

    long long res = 1LL * N * M;
    // now deduct bad pairs i.e. (i, j) s.t. gcd(i, j) > 1
    for (int d = 2; d <= N; d++) {
        if (!hasSquareFactor[d]) {
            int sign = (cntPrimeFactors[d] & 1) ? 1 : -1;
            // pairs with both coordinates multiple of d
            res -= sign * (N / d) * (M / d);
        }
    }

    printf("%lld\n", res);
    return 0;
}