Pagini recente » Atasamentele paginii Stalpi2 | Cod sursa (job #2326634) | Cod sursa (job #3360214) | Cod sursa (job #2326630) | Cod sursa (job #3359044)
#include <fstream>
using namespace std;
long long ciur1[1000010], ciur2[1000010];
long long c, d, i, j, sol, m;
long long f(long long x) {
return (c/x)*(d/x);
}
int main () {
ifstream fin ("mins.in");
ofstream fout("mins.out");
fin>>c>>d;
c--;
d--;
m = min(c,d); /// fac ciur pana la minimul dlong longre c si d pentru ca la numerele prime mai mari ca acest minim functia f va returna 0
for (i=2;i<=m;i++)
if (ciur1[i] == 0)
for (j=i;j<=m;j+=i)
ciur1[j] ++; /// toti multiplii lui i il au factor prim pe i
/// raman marcate cu 0 numerele prime
/// si elementele nenule sunt chiar numarul de factori primi
/// 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/// 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 1 2
sol = c*d;
/**
sol -= (suma din f(numar prim))
sol += (suma din f(produs de 2 numere prime distincte)) /// ne itereseaza 6 dar nu 12 sau 18
/// ne long longereseaza 21 (3*7) dar nu si 42 sau 63
sol -= (suma din f(produs de 3 numere prime distincte)) etc
Mai sus cu ciur am depistat numerele care sunt prime.
Pe mine ma long longereseaza mai mult:
- si numerele care sunt produs de numere prime disticte
- si produs de cati factori primi distincti sunt aceste numere ca
**/
/**
c = 9 si d = 12
sol = 9*12
sol -= f(2) /// eliminam toate perechile de numere cu cmmdc 2
sol -= f(3) /// eliminam toate perechile de numere cu cmmdc 3
4 nu ne long longereseaza
sol -= f(5) /// eliminam toate perechile de numere cu cmmdc 5
sol += f(6) /// punem la loc perechi de numere cu cmmdc 6
sol -= f(7) /// eliminam toate perechile de numere cu cmmdc 7
8 nu ne long longereseaza
9 nu ne long longereseaza
**/
/**
Ramane decizia daca un numar este sau nu produs de factori primi distincti si de cati astfel de factori ca paritate
solutia 1: factorizez cu descompunere in factori primi fiecare numar pana la 1000000 si numar ce imi trebuie
1000000 * sqrt(1000000) teoretic duce la miliard
**/
/**
Vom face altfel observand ca numerele rele sunt divizibile prlong longr-un patrat perfect de numar prim
Adica daca numarul nu e [rodus de factori primi distincti inseamna ca cel putin un factor prim apare in el cel putin la puterea a 2-a
Ex 40 = 2 ^ 3 * 5 se divide prim 2 ^ 2
**/
for (i=2;i<=m;i++)
if(ciur2[i] == 0)
for (j=i*i; j<=m; j+= i*i )
ciur2[j] = 1;
/// am marcat in ciur2 cu 1 numerele care nu sunt libere de patrate (divizibile prin cel putin un FP la o putere mai mare ca 1)
for (i=2;i<=m;i++)
if (ciur2[i] == 0) ///i este produs de factori primi distincti
if (ciur1[i] % 2 == 1) /// i are numar impar de factori primi
sol -= f(i);
else
sol += f(i);
/**
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 1 1 1 1 1
**/
fout<<sol;
}