Educational Codeforces Round 50 (Rated for Div. 2) F - Relatively Prime Powers(数学+容斥)

时间:2023-03-10 04:34:32
Educational Codeforces Round 50 (Rated for Div. 2) F - Relatively Prime Powers(数学+容斥)

题目链接:http://codeforces.com/contest/1036/problem/F

题意:Educational Codeforces Round 50 (Rated for Div. 2) F - Relatively Prime Powers(数学+容斥)

题解:求在[2,n]中,x != a ^ b(b >= 2 即为gcd)的个数,那么实际上就是要求x = a ^ b的个数,然后用总数减掉就好了,答案即为Educational Codeforces Round 50 (Rated for Div. 2) F - Relatively Prime Powers(数学+容斥)。(pow会丢失精度,学习避免精度丢失的方法)

 #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int MAXN = 1e5 + ;
const int MAXM = 2e6 + ;
const ll mod = 1e9 + ; bool check[];
int prime[];
int mu[]; void Moblus(int N) {
mst(check, false);
mu[] = ;
int tot = ;
for(int i = ; i <= N; i++) {
if(!check[i]) {
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot; j++) {
if(i * prime[j] > N) {
break;
}
check[i * prime[j]] = true;
if(i % prime[j] == ) {
mu[i * prime[j]] = ;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}
} int main()
{
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
Moblus();
int t;
scanf("%d",&t);
while(t--) {
ll n;
scanf("%lld",&n);
ll ans = ;
for(int i = ; i <= ; i++) {
if(!mu[i]) continue;
ll raiz = round(pow(n, 1.0 / i));
while(pow((long double)raiz, i) > (long double)n) raiz--;
while(pow((long double)raiz + , i) <= (long double)n) raiz++;
raiz--;
ans += (ll)mu[i] * raiz;
}
printf("%lld\n",n - + ans);
}
return ;
}