一. 题目描述
题目传送门 - Atcoder Beginner Contest383 - D. 9 Divisors
二. 思路分析
题意很简单明了,求 1 1 1 到 n n n 有多少个数有 9 9 9 个因数。注意 n ≤ 4 ∗ 1 0 12 n \leq 4*10^{12} n≤4∗1012。
我们设 x 2 x^2 x2 满足以上条件。那么一定有 x 2 x^2 x2 是一个完全平方数,因为只有完全平方数有奇数个因数,证明简单就不再赘述了。
所以,我们只需要枚举 x 2 = x \sqrt{x^2} = x x2=x 就可以了。
我们再设 x = a ∗ b x = a*b x=a∗b,则当 1 < a < b < x 1 < a < b < x 1<a<b<x 中, a a a 和 b b b 的取值是唯一的时,那么 x 2 x^2 x2 满足题目条件,对答案产生贡献。
证明不难,因为在满足上述条件的情况下, x 2 x^2 x2 的 9 9 9 个因数分别为 1 , a , b , a b , a 2 , b 2 , a 2 b , a b 2 , a 2 b 2 1,a,b,ab,a^2,b^2,a^2b,ab^2,a^2b^2 1,a,b,ab,a2,b2,a2b,ab2,a2b2。
那么,只要 a , b , a 2 , b 2 , a,b,a^2,b^2, a,b,a2,b2, 都不相等即可。枚举的时候判一下就可以了。具体地,如果 a = b 2 a = b^2 a=b2 或 b = a 2 b = a^2 b=a2 ,那么原来的两种情况会合并为一种。那么,如果 a a a 和 b b b 有且仅有两种取值并且都满足 a = b 2 a = b^2 a=b2 或 b = a 2 b = a^2 b=a2 ,此时这种情况就也是满足条件的了。
三. 代码实现
由于我们设 x = a ∗ b x = a*b x=a∗b 且 1 < a < b < x 1 < a < b < x 1<a<b<x,那么 x 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;
}