免费推广网站大全网_公司网页建立_什么是seo关键词优化_深圳互联网公司50强

一. 题目描述

题目传送门 - Atcoder Beginner Contest383 - D. 9 Divisors

二. 思路分析

题意很简单明了，求 $1$ 到 $n$ 有多少个数有 $9$ 个因数。注意 $n\le 4\ast 10^{12}$。

我们设 $x^2$ 满足以上条件。那么一定有 $x^2$ 是一个完全平方数，因为只有完全平方数有奇数个因数，证明简单就不再赘述了。

所以，我们只需要枚举 $\sqrt{x^2}=x$ 就可以了。

我们再设 $x=a\ast b$，则当 $1<a<b<x$ 中，$a$ 和 $b$ 的取值是唯一的时，那么 $x^2$ 满足题目条件，对答案产生贡献。

证明不难，因为在满足上述条件的情况下，$x^2$ 的 $9$ 个因数分别为 $1,a,b,ab,a^2,b^2,a^{2}b,a{b}^2,a^2{b}^2$。

那么，只要 $a,b,a^2,b^2,$ 都不相等即可。枚举的时候判一下就可以了。具体地，如果 $a=b^2$ 或 $b=a^2$ ，那么原来的两种情况会合并为一种。那么，如果 $a$ 和 $b$ 有且仅有两种取值并且都满足 $a=b^2$ 或 $b=a^2$ ，此时这种情况就也是满足条件的了。

三. 代码实现

由于我们设 $x=a\ast b$ 且 $1<a<b<x$，那么 $x$ 一定不是质数，这种情况可以提前判出来，就不需要找因数了。

#include <bits/stdc++.h>
using namespace std;
long long x,ans;
bool f[5000005];
long long fnd(long long n) 
{long long res = 0;for (long long i=2;i*i<n;i++){if (n % i == 0 && i*i != (n/i)) res+=2;if (n % i == 0 && i*i == n/i) res++;if (res > 2) break; //剪枝}return res;
}
int main()
{cin >> x;for (long long i=2;i*i<=x;i++){if (f[i] == 0) //判断质数{for (long long j=1;j*i*j*i<=x;j++){f[i*j] = 1;}continue;}if (fnd(i) == 2) {ans++;}}cout<<ans;return 0;
}