题解：AT_abc383_c [ABC383C] Humidifier 3

思路：
#

一个数若要恰好有九个约数，它必须是以下两种形式之一：

$p^8$，其中 $p$ 是一个质数。
$p^2 \cdot q^2$，其中 $p$ 和 $q$ 是不同的质数。

为什么是这两种形式，原因如下。

一个数的约数个数可以通过其质因数分解来确定。假设有一个正整数 $n$，它的质因数分解为：

$$ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k} $$

其中 $p_1, p_2, \ldots, p_k$ 是不同的质数，而 $e_1, e_2, \ldots, e_k$ 是这些质数在 $n$ 的质因数分解中的指数。

根据约数个数定理，$n$ 的约数个数 $d(n)$ 可以通过下面的公式计算得出：

$$ d(n) = (e_1 + 1)(e_2 + 1)\dots(e_k + 1) $$

要让 $n$ 恰好有九个约数，我们需要找到一种方法使得上述乘积等于 $9$。由于 $9$ 可以被分解为两个因数的乘积，即 $9 = 9 \times 1 = 3 \times 3$，因此我们可以得出两种可能的情况：

当我们有一个质数的八次幂时，比如 $p^8$，这时只有一个质因子，其指数加一等于 $9$，所以它有 $8 + 1 = 9$ 个约数。
当我们有两个不同质数的平方相乘时，比如 $p^2 \cdot q^2$，这时有两个质因子，每个的指数加一都等于 $3$，所以它们一起产生 $(2 + 1)(2 + 1) = 3 \times 3 = 9$ 个约数。

这两种情况是能使一个数恰好有九个约数的形式，因为除此之外没有其他方法可以将 $9$ 分解为大于 $1$ 的整数之积。这就是为什么我们要找的数必须是 $p^8$ 或者 $p^2 \cdot q^2$ 的形式。

代码：
#

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL n;
vector<bool>is_prime;
vector<LL>primes;
void hs1(LL lim){
	is_prime.assign(lim+1,1);
	is_prime[0]=is_prime[1]=0;
	for(LL i=2;i*i<=lim;i++){
		if(is_prime[i]){
			for(LL j=i*i;j<=lim;j+=i)is_prime[j]=0;
		}
	}
	for(LL i=2;i<=lim;i++)if(is_prime[i])primes.push_back(i);
}
LL solve(LL n){
	LL ans=0;
	int len=primes.size();
	for(LL i=0;i<len;i++){
		LL num=primes[i]*primes[i]*primes[i]*primes[i]*primes[i]*primes[i]*primes[i]*primes[i];
		if(num>n)break;
		ans++;
	}
	for(LL i=0;i<len;i++){
		LL a=primes[i]*primes[i];
		if(a*a>n)break;
		for(LL j=i+1;j<len;j++){
			LL num=a*primes[j]*primes[j];
			if(num>n)break;
			ans++;
		}
	}
	return ans;
}
int main(){
	cin>>n;
	hs1(static_cast<LL>(sqrt(n)));
	cout<<solve(n)<<"\n";
	return 0;
}

思路： #

代码： #

思路：
#

代码：
#