题目

Solution

当 f [ i ] f[i] f[i]表示满足 g c d ( k 1 , k 2 , k 3 … ) = i gcd(k_1, k_2, k_3 … )=i gcd(k1​,k2​,k3​…)=i的 x x x个数
假设没有任何限制，那么 2 k 1 ⋅ 3 k 2 ⋅ 5 k 3 . . . 2^{k_1}\cdot 3^{k_2}\cdot 5^{k_3}... 2k1​⋅3k2​⋅5k3​...可以表示所有数
所以 2 k 1 i ⋅ 3 k 2 i ⋅ 5 k 3 i . . . 2^{k_1i}\cdot 3^{k_2i}\cdot 5^{k_3i}... 2k1​i⋅3k2​i⋅5k3​i...可以表示 g c d ( k 1 , k 2 , k 3 … ) = = 0 ( m o d i ) gcd(k_1, k_2, k_3 … )==0(mod i) gcd(k1​,k2​,k3​…)==0(modi)的 x x x个数

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,i,j;
ll ans,f[60],n;
int main(){
	scanf("%d",&T);
	for (;T--;){
		scanf("%lld",&n);
		ans=n-1;
		for (i=59;i>1;i--){
			f[i]=pow(n,1.0/i)-1;
			for (j=i+i;j<60;j+=i) f[i]-=f[j];
			ans-=f[i];
		}
		printf("%lld\n",ans);
	}
}