Cod sursa(job #2963013)
Utilizator | Stanciu-Tivlea Valentin Gabriel bitza1247 | Data | 10 ianuarie 2023 00:05:05 |
---|---|---|---|
Problema | Principiul includerii si excluderii | Scor | 30 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.58 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long n,m,a,b,i,j,k,d,x,nr,s,prime[2000010],v[510];
bool ciur[2000010];
void precalc ( int n = 1000000 ) {
for ( int i = 2; i * i <= 2000000; i += 1 + i % 2 )
if ( ciur[i] == 0 )
{
k++;
prime[k]=i;
for ( int j = i * i; j <= 2000000; j += i )
ciur[j] = 1;
}
}
int main()
{
k=0;
precalc();
f>>n;
while(n)
{
f>>a>>b;
x=b;
k=0;
m=0;
s=0;
while(x>1)
{
m++;
d=prime[m];
if(x%d==0)
{
v[++k]=d;
while(x%d==0)
{
x=x/d;
}
}
if(d*d>x)
{
d=x;
}
}
for(i=1; i<(1<<k); i++)
{
x=1;
nr=0;
for(j=0; j<k; j++)
{
if((1<<j)&i)
{
// if(n==1)
// cout<<i<<' '<<j<<'\n';
x*=v[j+1];
nr++;
}
}
// if(n==1)
// cout<<" "<<x<<'\n';
if(nr%2==1)
{
s-=a/x;
}
else
{
s+=a/x;
}
}
// cout<<'\n';
g<<a-abs(s)<<'\n';
n--;
}
return 0;
}