Cod sursa(job #2241684)

Utilizator ElizaTElla Rose ElizaT Data 16 septembrie 2018 18:39:38
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("mins.in");
ofstream fout ("mins.out");

int c,d,nr[1000005];
bool pp[1000005];

void f()
{
    for (int i = 2;i <= c;i++)
    {
        if (!nr[i])
        {
            for (int j = i;j <= c;j += i)
                nr[j]++;
            if (1ll * i * i > c * 1ll)
                continue;
            for (int j = i * i;j <= c;j += i * i)
                pp[j] = 1;
        }
    }
}

int main()
{
    long long int ans;
    fin >> c >> d;
    c--;
    d--;
    if (c > d)
        swap(c, d);
    f();
    ans = 1LL * c * d;
    for (int i = 2; i <= c; i++)
    {
        if (pp[i])
            continue;
        if (nr[i] % 2)
            ans -= 1ll * (c / i) * (d / i);
        else
            ans += 1ll * (c / i) * (d / i);
    }
    fout << ans;
    return 0;
}