Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3363733) | Cod sursa (job #3363707)
#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;
}