Cod sursa(job #3276807)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 14 februarie 2025 19:24:43
Problema Cowfood Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>

using namespace std;

const int NMAX = 1e6;

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

int c, d;
long long sol, a, b;

char v[NMAX]; /// v[i] = Mobius(i) + 1

int main()
{
    fin >> c >> d;
    --c, --d;
    if(c > d) swap(c, d);
    for(int i = 2; i <= c; ++i)
    {
        if(v[i] == 1) continue; /// i nu este divizibil cu patratul unui nr prim
        a = 0, b = 0;
        if(v[i])
        {
            for(int j = i; j <= d; j += i)
            {
                --v[j];
                if(j <= c) ++a; /// Merg (i, j) si (j, i)
                else ++b; /// Merge doar (i, j)
            }
            sol -= a * (a + b);
        }
        else
        {
            for(int j = i; j <= d; j += i)
            {
                ++v[j];
                if(j <= c) ++a; ///Merg (i, j) si (j, i)
                else ++b; ///Merge doar (i, j)
            }
            sol += a * (a + b);
        }
    }
    fout << (long long)c*d - sol;
    return 0;
}