2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——C. You can't just take and divide（约数个数定理，因数个数定理） · znzryb
## 题目大意
**题目名称**：C. You can't just take and divide（你不能只是拿来分析）
**题目描述**：
Anatoly 和 Antitoly 对资源的分配有不同的看法。Antitoly 正在开发一个由参数 $n$ 定义的理想社会模型。你需要帮他计算在区间 $[1, n]$ 中，有多少个整数 $x$ 同时满足以下两个条件：
1. $x$ 是**奇数**。
1. $x$ 的**因子个数**是**奇素数**。
**输入格式**：
第一行包含一个奇整数 $n$ ($3 \le n \le 111^{13}$)。注意数据范围非常大，需使用能够处理大数的类型或高精度。
**输出格式**：
输出一个整数 $R$，表示满足条件的 $x$ 的个数。
**样例 1**
```
输入：
3
输出：
0
```
**样例 1 解释**：
- 1 的因子个数为 1（奇数但不是素数）。
- 2 是偶数。
- 3 的因子个数为 2（素数但不是奇数）。
没有满足条件的数。
**样例 2**
```
输入：
5
输出：
0
```
**样例 2 解释**：
- 接续样例 1，新增 4 和 5。
- 4 的因子个数为 3（奇素数），但 4 本身是偶数。
- 5 的因子个数为 2（偶素数）。
没有满足条件的数。
**样例 3**
```
输入：
9
输出：
1
```
**样例 3 解释**：
- 接续样例 2，新增 6, 7, 8, 9。
- 6, 8 是偶数。
- 7 的因子个数为 2。
- 9 是奇数，且因子为 1, 3, 9，共 3 个。3 是奇素数，满足所有条件。
故答案为 1。
**样例 4**
```
输入：
111
输出：
4
```
**样例 5**
```
输入：
9753113579
输出：
9563
```
## 思路讲解
[ABC-383-D - 9 Divisors ](/2025/02/02/20250202-b24822c7)
使用因数个数定理，或者说是约数个数定理。
其实使用约束个数定理不难得出如下的结论，那么 P 的 e1 次方就是我们所要枚举得出的这个数。
$$
p^{e1};\ e1+1,p\in\{3,5,7,11,\cdots\}（除了 2 的所有素因数）
$$
由于 e1 是从这个 2 开始的，所以我们**直接遍历**的时间复杂度是 $O(\sqrt n)$。
```cpp
void Solve() {
ll N;
cin >> N;
sieve(1e7);
ll ans=0;
// 我们这里实际上是在遍历的是 e1 加一。
for (auto e1:primes) {
if (e1==2) continue;
for (auto p:primes) {
if (p==2) continue;
__int128 num=1;
// 因为我们上面便利的是 e1+1，所以说这边就乘 e1-1 次。
for (int i=1;i<=e1-1;++i) {
num*=p;
}
if (num>N) {
if (p==3) {
cout<<ans<<"\n";
return;
}
break;
}else {
++ans;
}
}
}
}
```
## AC代码
::: 源代码
```cpp
/**
* Problem: C. You can't just take and divide
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106169/problem/C
* Created: 2026-02-15 12:07:18
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
// minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
minp.assign(n+5,0);
// minp[1]=1; // 加了这句话可能把 1 误判成素数，要小心
for(int i=2;i<=n;++i){
if(minp[i]==0){ // 是素数
minp[i]=i;
primes.push_back(i);
}
for(auto p:primes){
if(i*p>n){ // 超范围了
break;
}
minp[i*p]=p;
// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
// i * p_next = (p * k) * p_next 最小的应该是p
if(p==minp[i]){
break;
}
}
}
}
void Solve() {
ll N;
cin >> N;
sieve(1e7);
ll ans=0;
for (auto e1:primes) {
if (e1==2) continue;
for (auto p:primes) {
if (p==2) continue;
__int128 num=1;
for (int i=1;i<=e1-1;++i) {
num*=p;
}
if (num>N) {
if (p==3) {
cout<<ans<<"\n";
return;
}
break;
}else {
++ans;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106169/submission/362991651
*/
```
:::
## 心路历程（WA，TLE，MLE……）