9 Divisors

Problem Statement

找出不大于 $N$ 且恰好有 $9$ 个因数的正整数的个数。

Input

只有一行，一个整数 $N$。

Output

一行一个整数，表示答案。

Sample Input #1

1

200

Sample Output#1

1

3

Sample Input #2

1

4000000000000

Sample Output #2

1

407073

Constraints

$1 \leq N \leq 4 \times 10^{12}$
所有输入值均为整数。

样例一解释：

三个正整数 $36,100,196$ 满足条件。

Solving

题目要求求仅含9个因数的数字，我们由数论中的唯一分解定理可得：

所有自然数都可以表示为质数的乘积。

设 n $\in$ [1,N]。

一般的，一个数的因子都是$对称的$，这意味着a是n的因子，$\frac{a}{n}$也是n的因子，

而此时n有9个因子，说明n是$完全平方数$。

此时有:

$$ Divisors = \prod_{i=1}^k(a_i + 1)\space\space\space[N = \prod_{i=1}^kp_i^{a_i}] $$

此时我们得到了约数定理，n的约数个数d(n)即为:

$$ d(n) = (a_1 + 1)(a_2 + 1)(a_3 + 1)...(a_n + 1) $$

所以若一个数有9个因数，则我们可以得到两种情况：

其为某个质数的八次方，其9个因数分别为：($p^0,p^1,p^2,p^3,p^4 … p^8$)
其为某两个质数二次方的乘积，即($p_1^2*p_2^2$)

故此题的思路即为：

对$\sqrt{N}$以内的数进行线性筛，筛取素数。再根据单调性，用双指针试出所有质数(a,b)满足n=$a^2*b^2$,最后再暴力试出n = $p^8$计数即可。

时间复杂度O($\sqrt{N}lnln\sqrt{N}$)

 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


vector<int> pri;
bitset<1000010> not_prime;
int qpow(int x,int y)
{
    int res = 1;
    while(y>0)
    {
        if(y&1) res *= x;
        x *= x;
        y>>=1;
    }
    return res;
}
void Euler(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!not_prime[i])
        {
            pri.push_back(i);
        }
        for(int pri_j : pri)
        {
            if(pri_j*i>n) break;
            not_prime[pri_j*i] = true;
            if(i%pri_j==0) break;
        }
    }
}
int n;
void solve()
{
    Euler(1000000);
    cin >> n;
    int ans = 0;
    for(int i : pri)
    {
        int res = qpow(i,8);
        if(res<=n) ans++;
        else break;
    }
    int len = pri.size();
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<i;j++)
        {
            int res = qpow(pri[i],2)*qpow(pri[j],2);
            if(res<=n) ans++;
            else break;
        }
    }
    cout << ans;
}