当前位置: 首页 > >

NUIST OJ 1369 [2017 江苏科技大学 程序设计竞赛] B. Mr.Z 的四因子数 (数据加强版)

发布时间:

NUIST OJ 1369 [2017 江苏科技大学 程序设计竞赛] B. Mr.Z 的四因子数 (数据加强版)




NUIST OJ 1369 2017 江苏科技大学 程序设计竞赛 B MrZ 的四因子数 数据加强版
题目题目分析求素数表及欧拉函数表根据分解关系求数量
一个素数的三次方的情况两个不相等的素数的乘积 整体代码与运行结果随便说说后记



题目

题目描述



Mr.Z 是一多高超的数学大师,最喜欢研究的领域是数论,由于要经常做各类特殊的整数分布研充,所以他想麻烦你帮他解决一个问题。
考虑这样的一个数 K,它只含有四个因子,比如 10,它只有:1、2、5、10 这四个因子。我们将满足上述性质的数称为四因子数。
现在想请问你在区间 [ a, b ] 内有多少个四因子数。



输入描述



有多组测试数据,每组测试数据占一行。
每一行中,有两个用空格分隔的正整数 a 和 b。
a 和 b 均不超过 700000。



输出描述



对每组测试数据,输出一行答案。



样例输入



1 66666
1 666666



样例输出



15878
142481



题目分析

易得,四因子数可以为两个不相等的素数的乘积或者一个素数的三次方。
因此,题目就划归成为求素数表和根据分解关系求数量


求素数表及欧拉函数表

此处贴出我之前写的快速求素数表的方法
快速求素数表??埃氏筛法与欧拉筛法
详细就不再解释了


根据分解关系求数量
一个素数的三次方的情况

此处需要用到头文件


#include

这是为了使用下面的cbrt()函数
cbrt()函数的作用是开三次方。在欧拉函数中,可以直接求得在 1-T 的数字中,由一个素数的三次方组成四因子数的个数。


sum = pri[(int)cbrt(T)];
两个不相等的素数的乘积

两个不相等素数的乘积即使素数表中第1个开始,乘以第2个、第3个直到乘积即将大于 T 为止
结束本次循环之后,从第2个素数开始重复执行上述循环,直到素数的大小即将大于 T 的二次开方。


for (int i = 0, m, n, t = sqrt(T);; i++) {
m = pri[prime[i]];
n = pri[T / prime[i]];
if (prime[i]>t)
break;
else
sum += n - m;
}

整体代码与运行结果

/*code is far away from bug with the animal protecting
* ? ┏┓  ┏┓
*┏ ┛┻━━━┛┻┓
*┃     ┃  
*┃   ━   ┃
*┃  ┳┛ ┗┳  ┃
*┃       ┃
*┃   ┻   ┃
*┃      ┃
*┗━┓   ┏━┛
*  ┃   ┃神兽保佑
*  ┃   ┃代码无BUG!
*  ┃   ┗━━━┓
*  ┃       ┣┓
*  ┃       ┏┛
*  ┗┓┓┏━┳┓┏┛
*   ┃┫┫ ┃┫┫
*   ┗┻┛ ┗┻┛
*   
*/
#include
#include
#include
using namespace std;
#define LENGTH 701005
int is_prime[LENGTH];//是否是素数
int prime[LENGTH];//素数表
int pri[LENGTH];//欧拉函数表
int get(int T) {
int sum;
sum = pri[(int)cbrt(T)];
for (int i = 0, m, n, t = sqrt(T);; i++) {
m = pri[prime[i]];
n = pri[T / prime[i]];
if (prime[i]>t)
break;
else
sum += n - m;
}
return sum;
}
int main() {
int a, b;
memset(is_prime, 0, sizeof(int)*LENGTH);
memset(prime, 0, sizeof(int)*LENGTH);
memset(pri, 0, sizeof(int)*LENGTH);
for (int i = 2, t = 0, p = 0; i < LENGTH/2; i++) {
pri[i] = pri[i - 1];
if (is_prime[i] == 0)
{
prime[p++] = i;
pri[i]++;
}
for (int j = 0; j is_prime[i*prime[j]] = 1;
if (i%prime[j] == 0)
break;
}
}
while (cin >> a >> b) {
cout << get(b) - get(a - 1) << endl;
}
return 0;
}

似乎神兽在MarkDown里面出了点问题大家不要在意这个细节


结果如下


随便说说

在查询量很大的时候,这题目还可以用差分进行优化,以此达到高效多组查询的目的。
然而偷懒的我就不写在这里。


后记

照例感谢 ThinkSpirit诸位大佬的支持

附上大佬的题解



友情链接: