Cod sursa(job #2952733)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 9 decembrie 2022 20:31:09
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e6 + 7;

int a[NMAX], b[NMAX];

int main()
{
    int c, d;
    fin >> c >> d;
    c--;
    d--;

    int minim = min(c, d);
    long long ans = 1LL * c * d;

    for (int i = 2; i <= minim; i++)
    {
        if (a[i] == 0)
        {
            for (int j = 1; 1LL * j * i <= minim; j++)
            {
                a[1LL * i * j]++;
            }
            for (int j = 1; 1LL * j * i * i <= minim; j++)
            {
                b[j * i * i] = 1;
            }
        }

        if (b[i] == 0)
        {
            long long val = 1LL * (c / i) * (d / i);
            if (a[i] % 2 == 1)
            {
                ans -= val;
            }
            else
            {
                ans += val;
            }
        }
    }

    fout << ans;
    return 0;
}