Pagini recente » Istoria paginii grigore-moisil-2011/clasament/11-12 | progresii3 | Rating Dragomirescu Mihail (reveng3) | Rezultatele filtrării | Cod sursa (job #448218)
Cod sursa(job #448218)
#include <stdio.h>
#include <string.h>
#define MAXRAD 1000010
int P[50000];
bool prim[MAXRAD];
long long A, B, sum;
int T, D[20];
inline void factori()
{
memset(prim, true, sizeof(prim));
P[++P[0]] = 2;
for (int i=3; i<MAXRAD; i+=2)
if (prim[i]){
P[++P[0]] = i;
for (int j=3*i; j<MAXRAD; j+=(i<<1))
prim[j] = false;
}
}
void back(int lv, long long prod, int nr)
{
if (lv == D[0]+1){
if (nr&1 == 1)
sum -= (A / prod);
else
sum += (A / prod);
}
else{
back(lv+1, prod*D[lv], nr+1);
back(lv+1, prod, nr);
}
}
inline void solve()
{
scanf("%lld %lld",&A, &B);
D[0] = 0; sum = 0;
for (int i=1; i<P[0] && B/P[i] >= P[i]; i++)
if (B%P[i] == 0){
D[++D[0]] = P[i];
while (B%P[i] == 0)
B/=P[i];
}
if (B!=1) D[++D[0]] = (int)B;
back(1,1,0);
printf("%lld\n",sum);
}
int main()
{
freopen("pinex.in","r",stdin);
freopen("pinex.out","w",stdout);
factori();
for (scanf("%d",&T); T; T--)
solve();
return 0;
}