Pagini recente » Monitorul de evaluare | Antobroasca | Borderou de evaluare (job #2514932) | Borderou de evaluare (job #2746636) | Cod sursa (job #1591830)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#define X 1000000
using namespace std;
vector<bool> p; //numerelele prime generate
long long A, B, M;
int nrp;
vector<int> fact; //nrp = numarul de numere prime pana la 10^6
void ciurEratostene()
{
p.assign(X/2 +1, 1); //numerele prime mai mici decat 10^6
for(int i=1; (i<<1)+1 <= X; ++i)
if(p[i])
{
nrp++;
for(int j=3*i+1; (j<<1) <= X; j+=(i<<1) + 1)
p[j]=0;
}
}
void descInFactoriPrimi()
{
int iFactor=0, factor; //al i-lea factor prim din desc. lui B
double radB=sqrt(B); //evitam sa recalculam sqrt(B)
vector<int>().swap(fact);
if(B % 2 == 0)
{
fact.push_back(2);
while(B % 2 == 0)
B /= 2;
}
while(B>1)
{
iFactor++;
if(p[iFactor])
{
factor=iFactor*2 + 1;
if(B % factor == 0)
{
fact.push_back(factor);
while(B % factor == 0)
B /= factor;
}
if(B>1 && factor > radB) //ultimul factor prim
{
fact.push_back(B);
break;
}
}
}
}
void rezolva()
{
descInFactoriPrimi();
long long nrIntersectii =( 1 << (fact.size()) ) -1, Rez=0;
long long produs; //nr de intersectii/submultimi
int nrFactori = fact.size(), nrSubm;
for(long long i=1; i<=nrIntersectii; i++)
{
produs=1; nrSubm=0; //nr submultimilor intersectate
for(long long j=0; j<nrFactori; j++)
if( i & (1<<j) ) //i are bitul j
{
produs *= fact[nrFactori-j-1];
nrSubm++;
}
if(nrSubm % 2 ==1)
Rez += A/produs;
else
Rez -= A/produs;
}
cout<<A - Rez<<'\n';
}
int main()
{
freopen("pinex.in", "rt", stdin);
freopen("pinex.out", "wt", stdout);
ciurEratostene();
scanf("%lld", &M);
for(int i=1; i<=M; i++)
{
scanf("%lld%lld", &A, &B);
rezolva();
}
}