Cod sursa(job #1897204)

Utilizator antanaAntonia Boca antana Data 1 martie 2017 11:37:43
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <algorithm>

#define MAXN 1000001

using namespace std;

int sieve[MAXN];
bool bad[MAXN];

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

    int prime, n, m;
    long long ans, i;

    scanf("%d%d", &n, &m);

    n--;
    m--;
    ans = 1LL*n*m;
    if(n > m) swap(n, m);

    for(prime=2; prime<=n; ++prime)
        if(!sieve[prime]) {
            for(i=prime; i<=n; i+=prime)
                sieve[i]++;
            for(i=1LL*prime*prime; i<=n; i+=prime*prime)
                bad[i] = 1; }

    for(i=2; i<=n; ++i){
        if(bad[i]) continue;
        else {
            if(sieve[i]&1) ans -= 1LL*(n/i)*(m/i);
            else ans += 1LL*(n/i)*(m/i); } }

    printf("%lld", ans);


    return 0;
}