Pagini recente » Cod sursa (job #1720482) | Cod sursa (job #1949991)
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
const int MAXB = 1000005;//B este pana la 10^12, dar folosim doar sqrt(B)
bool neprim[MAXB];
int prime[80002];
void preprocesare()
{
for (int i = 2;i * i < MAXB;++i)
if (!neprim[i])
for (int j = i * i;j < MAXB;j += i)
neprim[j] = true;
for (int i = 2;i < MAXB;++i)
if (!neprim[i])
prime[++prime[0]] = i;
}
long long A,B;
void rezolvare()
{
long long factori[30] = {0};
long long d = 0;
while(B > 1)//descompunere in factori primi
{
++d;
if (B % prime[d] == 0)
{
factori[++factori[0]] = prime[d];
while(B % prime[d] == 0)
B /= prime[d];
}
if (B > 1 && prime[d] > sqrt(B))
{
factori[++factori[0]] = B;
B = 1;
}
}
long long solutie = A;//Din A numere vom scadea cele care sunt neprime cu B
//generam toate submultimile de factori folosind operatii pe biti
for (int i = 1;i < (1 << factori[0]);++i)
{
char nr = 0;
long long prodfact = 1;
for (int j = 0;j < factori[0];++j)
if (((1 << j) & i) != 0)//elementul j apare in aceasta submultime formata din bitii lui i
{
++nr;
prodfact *= factori[j + 1];
}
if (nr % 2 == 0)//cele cu numar par sunt incluse
solutie += A / prodfact;
else//cele cu numar impar sunt excluse
solutie -= A / prodfact;
}
out << solutie << '\n';
}
int main()
{
preprocesare();
int nr_teste;
in >> nr_teste;
while (nr_teste > 0)
{
in >> A >> B;
rezolvare();
--nr_teste;
}
return 0;
}