Pagini recente » Cod sursa (job #1859961) | Cod sursa (job #758750) | Cod sursa (job #903177) | Cod sursa (job #2691287) | Cod sursa (job #396894)
Cod sursa(job #396894)
# include<stdlib.h>
# include<stdio.h>
# define FIN "pinex.in"
# define FOUT "pinex.out"
# define NMAX 1000000
using namespace std;
char prim [ NMAX ] ;
long long np [NMAX],dv[NMAX] ;
long long A,B,T;
void ciur()
{for ( long long i=1; i<NMAX; i++ )
prim [ i ] = 1;
for(long long i=2;i<NMAX;i++)
if(prim[i])
{for(long long j=i+i;j<=NMAX;j+=i)
prim[i]=0;
np[++np[0]]=i;}
}
void rez()
{long long nrdiv=0;long long sol;
for(long long i=1;np[i]*np[i]<=B;i++)
{if(B%np[i]==0)
{while(B%np[i]==0) B=B/np[i];
dv[++nrdiv]=np[i];}
}
if(B>1) {dv[++nrdiv]=B;B=1;}
long long bin=1<<nrdiv;
sol=A;
for(long long i=1;i<bin;i++)
{long long nr=0;long long rez=1;
for (long long j=0;j<nrdiv;j++)
if((1<<j) & i) {rez=(long long )rez* dv[j+1];
nr++;}
if(nr%2) nr=-1;
else nr=1;
sol=(long long)sol+(long long)nr*A/rez;
}
printf("%lld\n",sol);
}
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&T);
ciur();
for(;T;T--)
{scanf("%lld %lld",&A,&B);
rez();
}
return 0;}