Cod sursa(job #2153455)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 6 martie 2018 11:06:31
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#define DM 1000005
#define inf 0x3f3f3f3f
#include <bitset>
#include <fstream>
using namespace std;

ifstream fi ("mins.in");
ofstream fo ("mins.out");
bitset <DM> bs;
int a, b, dv[DM];
long long sol;

int main()
{
    fi >> a >> b;
    --a;
    --b;
    if (a > b)
        swap(a, b);
    sol = 1LL*a*b;
    for (int i = 2; i <= a; ++i)
        dv[i] = inf;
    for (int i = 2; i*i <= a; ++i)
        if (!bs[i])
            for (int j = i*i; j <= a; j += i)
                bs[j] = 1;
    for (int i = 2; i <= a; ++i)
        if (!bs[i])
            for (int j = a/i; j > 0; --j)
                if (dv[j] != inf)
                    dv[i*j] = 1 + dv[j];
    for (int i = 2; i <= a; ++i)
        if (dv[i] != inf)
        {
            if (dv[i]%2 == 1)
                sol -= 1LL*(a/i)*(b/i);
            else
                sol += 1LL*(a/i)*(b/i);
        }
    fo << sol;
    return 0;
}