Cod sursa(job #2974050)

Utilizator 100pCiornei Stefan 100p Data 2 februarie 2023 23:16:20
Problema Mins Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>

#define MAX 1000000
#define int long long
#define fastio ios_base::sync_with_stdio(0);\
               cin.tie(0), cout.tie(0);

#define FILES freopen("mins.in","r",stdin);\
              freopen("mins.out","w",stdout);

using namespace std;

int ans, ox[MAX + 5], oy[MAX + 5], n, m, nrPrime[MAX + 5];
bool ciur[MAX + 5], good[MAX + 5];

signed main()
{
    fastio
    FILES
    std::cin >> n >> m;
    for(int i = 1; i < max(n, m); ++i)
    {
        if(i < m) oy[i]++;
        if(i < n) ox[i]++;
    }
    nrPrime[2] = 1;
    for(int i = 4; i <= MAX; i += 2)
    {
        ciur[i] = 1;
        if(i % 4 == 0)
            good[i] = 1;
        nrPrime[i]++;
    }
    for(int i = 3; i <= MAX; i += 2)
    {
        if(!ciur[i])
        {
            nrPrime[i] = 1;
            for(int j = i + i; j <= MAX; j += i)
            {
                ciur[j] = 1;
                if(j >= i * i && j % (i * i) == 0)
                    good[j] = 1;
                nrPrime[j]++;
            }
        }
    }
    for(int i = 2; i < m; ++i)
    {
        if(!good[i])
        {
            int y = 0, x = 0, xx = 0, yy = 0;
            for(int j = i; j < max(m, n); j += i)
            {
                if(j < min(n, m))
                    y += oy[j], x += ox[j];
                else
                    yy += oy[j], xx += ox[j];
            }

            if(nrPrime[i] % 2)
            {
                ans += x * y;
                if(yy)
                    ans += yy * x;
                else
                    ans += xx * y;
            }
            else
            {
                ans -= x * y;
                if(yy)
                    ans -= yy * x;
                else
                    ans -= xx * y;
            }
        }
    }

    std::cout << 1LL * (n - 1) * (m - 1) - ans << '\n';
}