题解 007 题目 AT_abc383_d

array2022 · 2024-12-08 10:33:43 · 题解

说在前面

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

题目分析

• 首先我们知道，对 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 提交记录和洛谷评测记录。

通过代码

#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;
}