Cod sursa(job #1653690)

Utilizator akaprosAna Kapros akapros Data 16 martie 2016 14:00:55
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
#define maxN 1000002
#define ll long long
using namespace std;
int n, c, d, p[maxN], pp[maxN];
ll ans;
void read()
{
    freopen("mins.in", "r", stdin);
    scanf("%d %d", &c, &d);
    -- c; -- d;
    n = min(c, d);
}
void solve()
{
    int i, j;
    ans = 1LL * c * d;
    for (i = 2; i <= n; ++ i)
    {
        if (!p[i])
    {
        for (j = i; j <= n; j += i)
            ++ p[j];
        if (1LL * i * i <= 1LL * n)
            for (j = i * i; j <= n; j += i * i)
                pp[j] = 1;
    }
       if (!pp[i])
       {
           if (p[i] % 2)
              ans -= 1LL * (c / i) * (d / i);
           else
            ans += 1LL * (c / i) * (d / i);
       }
    }
}
void write()
{
    freopen("mins.out", "w", stdout);
    printf("%lld", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}