Znzryb's Blog
0%

ABC-383-D - 9 Divisors 

Posted on Edited on

题目大意

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

输入格式：

  • 一行一个整数 NN （ 1≤N≤4×10121 \leq N \leq 4 \times 10^{12} ）

输出格式：

  • 一个整数，表示答案

样例说明：

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

思路讲解

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

这篇解释了该定理

image

AC代码

https://atcoder.jp/contests/abc383/submissions/62341051

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 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;
}
/*

*/