ABC-383-D - 9 Divisors · znzryb

## 题目大意

给定正整数 $N$，求不超过 $N$ 的正整数中，恰好有 9 个正约数的数的个数。

**输入格式：**

- 一行一个整数 $N$ （ $1 \leq N \leq 4 \times 10^{12}$ ）

**输出格式：**

- 一个整数，表示答案

**样例说明：**

- 当 $N = 200$ 时，满足条件的正整数有 36, 100, 196 共 3 个

## 思路讲解

约数个数定理（因数个数定理）

这篇解释了该定理

[](https://www.notion.so/1cf4539447bd8059b93ac6ab28bc9518) 

![image](https://media.znzryb.com/20250202-b24822c7/image_3d1b2789.png)

## AC代码

[https://atcoder.jp/contests/abc383/submissions/62341051](https://atcoder.jp/contests/abc383/submissions/62341051)

```cpp
// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(4e6)+10,MAXval=static_cast<ll>(5e18)+3;

ll N;
bool isprime[MAXN];
ll prime[MAXN];
inline void genPrimels(ll range){
	FOR(i,2,range){	// 0,1 比较特殊
		isprime[i]=true;
	}
	for(int i=2;i*i<=range;++i){
		for(int j=i*2;j<=range;j+=i){
			isprime[j]=false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll ans=0;
	ll sqrtN=floor(sqrt(N));
	genPrimels(sqrtN);
	ll idx=0;
	FOR(i,2,sqrtN){
		if(isprime[i]) prime[++idx]=i;
	}
	// deEnter(idx);
	ll flag=idx;
	FOR(i,1,idx){
		ROF(j,flag,1){
			if(prime[i]*prime[j]<=sqrtN){
				flag=j;
				break;
			}
		}
		if(flag<=i) break;
		ans+=flag-i;
	}
	FOR(i,1,idx){
		if(prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]<=N){
			++ans;
		}else{
			break;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62341051
*/
```

## 心路历程（WA，TLE，MLE……）

暴力，TLE

```cpp
// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e6)+10,MAXval=static_cast<ll>(5e18)+3;

ll N;
inline bool check(ll x){
	ll res=0;
	for(int i=1;i*i<=x;++i){
		if(i*i==x){
			++res;
		}else if(x%i==0){
			res+=2;
		}
		if(res>9) return false;
	}
	if(res==9) return true;
	else return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll ans=0;
	for(int i=1;i*i<=N;++i){
		if(check(i*i)){
			++ans;
			deEnter(i*i);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*

*/
```