Pagini recente » Cod sursa (job #2359676) | Cod sursa (job #550376) | Cod sursa (job #1956717) | Cod sursa (job #2925415) | Cod sursa (job #2698965)
#include <iostream>
#include <fstream>
#define NMAX 1000000
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
bool pr[NMAX+1]; //= radical din 10^12
//caut numerele prime pana la radical din b
int prim[79000];
long long v[79000];
int main()
{
int teste;
int i, j, totalprim=0;
long long a, b, ct, n, nrc, p, rez;
//ciurul lui Eratostene
for(i=4; i<=NMAX; i+=2) pr[i]=1;
for(i=3; i*i<=NMAX; i+=2) if(pr[i]==0)for(j=i*i; j<=NMAX; j+=i) pr[j]=1;
for(i=2; i<=NMAX; i++)
{
if(pr[i]==0)
{
prim[++totalprim]=i;
}
}
//cout<<totalprim<<"\n";
fin>>teste;
while(teste--)
{
fin>>a>>b;
rez=a;
ct=1;
n=0;
while(b>1&&prim[ct]*prim[ct]<=b)
{
if(b%prim[ct]==0) v[++n]=prim[ct];
while(b%prim[ct]==0) b=b/prim[ct];
ct++;
}
if(b>1) v[++n]=b;
for(i=1; i<(1<<n); i++)
{
nrc=0; p=1;
for(j=0; j<n; j++)
{
if(i&(1<<j))
{
nrc++;
p=p*v[j+1];
}
}
if(nrc%2==1) rez=rez-a/p;
else rez=rez+a/p;
}
fout<<rez<<"\n";
}
return 0;
}