Cod sursa(job #2878144)

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

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

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

bool check(int val)
{
    if (val % 4 == 0)
        return 0;
    return !c[val];
}

int nr(int val)
{
    if (val % 2 == 0 and val != 2)
        ciur[val] = 1;
    if (!ciur[val])
        return 1;
    int ans = nrp[val];
    if (val % 2 == 0)
        ans++;
    return ans;
}
int 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 = (c - 1) * (d - 1);
    for (int i = 2; i <= mn; i++)
        if (check(i))
        {
            //cout << i << " " << nr(i) << "\n";
            if (nr(i) % 2 == 0)
                ans += 1LL * ((c - 1) / i) * ((d - 1) / i);
            else
                ans -= 1LL * ((c - 1) / i) * ((d - 1) / i);

        }
    cout << ans;
}