Pagini recente » Cod sursa (job #3360328) | Cod sursa (job #3360178) | Cod sursa (job #3360216) | Cod sursa (job #3360217) | Cod sursa (job #3359281)
#include <fstream>
#define DIM 1000100
using namespace std;
long long c, d, sol, i, j, m, x;
long long f(long long x) {
return (c/x) * (d/x);
}
long long ciur1[DIM];
long long ciur2[DIM];
/// cum pot decide mai repede decat n radical(n) daca un numar de pana in n e liber de patrate (produs de factori primi distincri)
/// 5 * 7^3 se divide prin 7^2 (nu e liberde patrate)
int main () {
ifstream fin ("mins.in");
ofstream fout("mins.out");
fin>>c>>d;
c--;
d--;
m = min(c,d);
for (i=2;i<=m;i++)
if (ciur1[i] == 0)
for (j=i;j<=m;j+=i)
ciur1[j]++; /// ciur1[numar] = numarul de factori primi ai lui "numar"
for (i=2;i<=m;i++)
if (ciur1[i] == 1) /// daca e prim
for (j=i*i;j<=m;j+=i*i)
ciur2[j] = 1; /// marchez in ciur2 doar multiplii patratelor de numere prime
sol = c*d;
for (x=2;x<=min(c,d);x++)
if ( ciur2[x] == 0 ) /// x este produs de factori primi distincti
if (ciur1[x] % 2 == 1) ///x are numar impar de factori primi
sol -= f(x);
else
sol += f(x);
fout<<sol;
return 0;
}
/**
for (i=1;i<=c;i++) 5000 * 5000 * log
for (j=1;j<=d;j++)
if (gcd(i,j) == 1)
sol++;
**/