Pagini recente » Cod sursa (job #2282880) | Borderou de evaluare (job #3184753) | Borderou de evaluare (job #2204100) | Cod sursa (job #1993126) | Cod sursa (job #956519)
Cod sursa(job #956519)
#include <iostream>
#include <fstream>
using namespace std;
int nr;
long long div[20],sum=0;
bool ok[20];
void descompune(int x)
{
int i;
nr=0;
for(i=2;i*i<=x;++i)
{
if(x%i==0)
{
div[++nr]=i;
while(x%i==0)
x/=i;
}
}
if(x!=1)
{
div[++nr]=x;
}
}
void bkt(int pos ,int a)
{
int i,k=0;
long long aux=1;
if(pos==nr)
{
for(i=1;i<=nr;++i)
{
if(ok[i])
{
++k;
aux*=div[i];
}
}
if(k%2==1)
{
sum-=a/aux;
}
else
sum+=a/aux;
return;
}
ok[pos+1]=true;
bkt(pos+1,a);
ok[pos+1]=false;
bkt(pos+1,a);
}
int main()
{
ifstream in("pinex.in");
ofstream out("pinex.out");
int m,i;
long long a,b;
in>>m;
for(i=1;i<=m;++i)
{
in>>a>>b;
sum=0;
descompune(b);
bkt(0,a);
out<<sum<<"\n";
}
return 0;
}