Cod sursa(job #3363707)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 21 august 2026 16:06:05
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
typedef long long ll;
const int DIM = 1e6;
int c, d;
int ciur1[DIM + 3], ciur2[DIM + 3];
///ciur1[n] = cati factori primi distincti are n
///ciur2[n] = daca are un factor prim la o putere >= 2

inline void prelucru() {
    for(int i=2; i<=DIM; i++)
        if(ciur1[i] == 0) //prim
            for(int j=i; j<=DIM; j+=i) ciur1[j]++;
    for(int i=2; i*i<=DIM; i++)
        if(ciur1[i] == 1) //prim
            for(int j=i*i; j<=DIM; j+=i*i) ciur2[j] = 1;
}

int main()
{
    prelucru();
    fin >> c >> d, c--, d--;
    ll rez = c * d; ///presupun ca fiecare punct are dreapta ei
    ///voi scadea produsele de nr impar de prime si le voi aduna pe cele cu nr par sa elimin suprapunerile
    ///cate puncte din (c, d) se impart la x => (c / x) * (d / x) => tre sa merg cu x pana la min(c, d)
    int minim = min(c, d);
    for(int i=2; i<=minim; i++) {
        if(ciur2[i] == 0) { //iau doar produsele de factori primi la ^1
            if(ciur1[i] % 2 == 1) rez -= (c / i) * (d / i);
            else rez += (c / i) * (d / i);
        }
    }
    fout << rez;

    return 0;
}