2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——C. You can't just take and divide（约数个数定理，因数个数定理）

题目大意

题目名称：C. You can’t just take and divide（你不能只是拿来分析）

题目描述：
Anatoly 和 Antitoly 对资源的分配有不同的看法。Antitoly 正在开发一个由参数 $n$ 定义的理想社会模型。你需要帮他计算在区间 $[1, n]$ 中，有多少个整数 $x$ 同时满足以下两个条件：

1. $x$ 是奇数。

2. $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 

使用因数个数定理，或者说是约数个数定理。

其实使用约束个数定理不难得出如下的结论，那么 P 的 e1 次方就是我们所要枚举得出的这个数。

$$p^{e1};\ e1+1,p\in\{3,5,7,11,\cdots\}（除了 2 的所有素因数）$$

由于 e1 是从这个 2 开始的，所以我们直接遍历的时间复杂度是 $O(\sqrt n)$。

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代码

源代码

/**
 * 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……）