Pagini recente » Cod sursa (job #1479223) | Cod sursa (job #2384013) | Cod sursa (job #955995) | Cod sursa (job #2025606) | Cod sursa (job #1854327)
#include <fstream>
#include <bitset>
using namespace std;
ofstream fout ("pinex.out");
ifstream fin ("pinex.in");
bitset <1000001> prim;
int diviz[1000001],divizb[25],pozdiv,t,poz;
long long a,b;
void ciur()
{
prim[ 1 ] = 1;
for( int i = 2 ; i <= 1000000 ; i ++ )
{
if( prim[ i ] == 0 )
{
for( int j = i * 2 ; j <= 1000000 ; j += i )
prim[ j ] = 1;
}
}
poz = 0;
for( int i = 2 ; i <= 1000000 ; i++ )
if( prim[ i ] == 0 )
diviz[ ++poz ] = i;
}
void solve( long long a , long long b )
{
pozdiv = 0;
long long rsp = 0;
for( int i = 1 ; i <= poz ; i++ )
{
if( b % diviz[ i ] == 0 )
{
divizb[ ++pozdiv ] = diviz[ i ];
while( b % diviz[ i ] == 0 )
b /= diviz[ i ];
}
}
if( b != 1 )
divizb[ ++pozdiv ] = b;
for( int i = 1 ; i < ( 1 << pozdiv ) ; i++ )
{
long long produs = 1;
int nrdiv = 0;
for( int j = 0 ; j < pozdiv ; j++ )
{
if( i & ( 1 << j ) )
{
nrdiv++;
produs *= divizb[ j + 1 ];
}
}
if( nrdiv % 2 )
rsp += a / produs;
else
rsp -= a / produs;
}
fout<<a - rsp<<'\n';
}
int main()
{
fin>>t;
ciur();
while( t-- )
{
fin>>a>>b;
solve( a , b );
}
}