Cod sursa(job #3297245)

Utilizator rapidu36Victor Manz rapidu36 Data 22 mai 2025 10:00:40
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <vector>

using namespace std;

vector <int> nr_dp;
vector <int> p_dp;

void ciur(int n)
{
    nr_dp.resize(n, 0);
    p_dp.resize(n, 1);
    for (int d = 2; d < n; d++)
    {
        if (nr_dp[d] == 0)
        {
            for (int m = d; m < n; m += d)
            {
                nr_dp[m]++;
                p_dp[m] *= d;
            }
        }
    }
}

long long nr_puncte(int c, int d)
{
    int n = min(c, d);
    ciur(n);
    long long nr = 0;
    for (int i = 1; i < n; i++)
    {
        if (p_dp[i] == i)
        {
            long long fr_red = (long long)((c - 1) / i) * ((d - 1) / i);
            if (nr_dp[i] % 2 == 0)
            {
                nr += fr_red;
            }
            else
            {
                nr -= fr_red;
            }
        }
    }
    return nr;
}

int main()
{
    ifstream in("mins.in");
    ofstream out("mins.out");
    int c, d;
    in >> c >> d;
    out << nr_puncte(c, d) << "\n";
    in.close();
    out.close();
    return 0;
}