Cod sursa(job #2878104)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 martie 2022 20:06:25
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 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 * i <= NMAX; i += 2)
        if (!ciur[i])
        {
            for (int j = i * i; j <= NMAX; j += (i << 1))
            {
                ciur[j] = 1;
                nrp[j]++;
            }
            int p = i * i;
            for (int 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 (ciur[val] == 0)
        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, d);
    long long ans = (c - 1) * (d - 1);
    for (int i = 2; i < mn; i++)
        if (check(i))
        {
            if (nr(i) % 2 == 0)
                ans += (c / i) * (d / i);
            else
                ans -= (c / i) * (d / i) - 1;

        }
    cout << ans;
}