题解 007 题目 AT_abc383_d

说在前面

这是我赛时的做法，并不是很优秀，时间复杂度似乎是错的，但是可以通过，因此分享出来，欢迎大家指正。

题目分析

首先我们知道，对 $n$ 分解质因数有 $n=\prod\limits_{i=1}^n p_i^{a_i}$ ，其中 $p_i$ 为质数， $a_i$ 为正整数，那么 $n$ 的因数个数为 $\prod\limits_{i=1}^n (a_i+1)$ 。
题目要求求有 $9$ 个因数的数，那么这个数肯定能表示成 $p_1^2 \cdot p_2^2$ 或 $p^8$ 的形式， $p_1,p_2,p$ 均为质数，直接分类讨论即可。
可以先筛出或打表出所有的质数，缩短运行时间。最后的时间复杂度 $O(n^{0.75})$ ，有超时的风险，但实测并不会超时，可以参考代码中的一些小技巧。在此贴出AtCoder 提交记录和洛谷评测记录。

通过代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool ip[4000005];
int n,ans;
bool check1(int x){
	if (!ip[x]) return 0;
	// 如果 x 是质数可以直接跳过，x 肯定不会超过 2e6，可以直接判断。
	for (int i=2;i*i<x;i++){
		if (x%i!=0) continue;
		if ((!ip[i])&&(!ip[x/i])) return 1;
		else return 0; // 直接返回 0 可以缩短运行时间。
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	ip[1]=1;
	for (int i=2;i<=2000;i++){
		if (ip[i]==0){
			for (int j=i*2;j<=4000000;j+=i){
				ip[j]=1;
			}
		}
	} // 埃氏筛。
	for (int i=2;i*i<=n;i++){
		if (check1(i)) ans++;
	} // 情况 1。
	for (int i=2;i*i*i*i*i*i*i*i<=n;i++){
		if (!ip[i]) ans++;
	} // 情况 2。
	cout<<ans;
	return 0;
}

题解 007 题目 AT_abc383_d

文章操作

说在前面

题目分析

通过代码

相关推荐

评论

题解 007 题目 AT_abc383_d