Cod sursa(job #2878155)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 martie 2022 21:51:31
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 1000003;

bool c[NMAX];
bool ciur[NMAX];
int nrp[NMAX];

void erat()
{
    for (int i = 3; i * i < NMAX; i += 2)
        if (!ciur[i])
        {
            int val = (i << 1);
            for (int j = i * i; j < NMAX; j += val)
                ciur[j] = 1;
        }
    for (int i = 3; i < NMAX; i += 2)
        if (!ciur[i])
        {
            long long p = 1LL * i * i;
            for (long long j = p; j < NMAX; j += p)
                c[j] = 1;
            for (int j = i; j < NMAX; j += i)
                nrp[j]++;
        }
}

bool check(int val)
{
    if (((val & 1) == 0) and ((val >> 1) & 1) == 0)
        return 0;
    return !c[val];
}

int nr(int val)
{
    if ((val & 1) == 0 and val != 2)
        ciur[val] = 1;
    if (!ciur[val])
        return 1;
    return nrp[val] + (!(val & 1));
}

int aux[] = {1, -1};
signed main()
{
    ifstream cin("mins.in");
    ofstream cout("mins.out");
    erat();
    int c, d;
    cin >> c >> d;
    int mn = min(c - 1, d - 1);
    long long ans = 1LL * (c - 1) * (d - 1);
    for (int i = 2; i <= mn; i++)
        if (check(i))
        {
            //cout << i << " " << nr(i) << "\n";
            ans += 1LL * ((c - 1) / i) * ((d - 1) / i) * aux[(nr(i) & 1)];
        }
    cout << ans;
}