当前位置: 首页> 健康> 科研 > 免费推广网站大全网_公司网页建立_什么是seo关键词优化_深圳互联网公司50强

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

时间:2025/7/10 17:22:06来源:https://blog.csdn.net/weixin_52163022/article/details/144317665 浏览次数:0次
免费推广网站大全网_公司网页建立_什么是seo关键词优化_深圳互联网公司50强

一. 题目描述

题目传送门 - 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} n41012

我们设 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=ab,则当 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=ab 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;
}
关键字:免费推广网站大全网_公司网页建立_什么是seo关键词优化_深圳互联网公司50强

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: