1362:[2017 江苏科技大学 程序设计竞赛] B. Mr.Z 的四因子数 (改编)

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

题目描述:

http://tool.vicz.cn/mirror/?pid=1362

http://tool.vicz.cn/mirror/?pid=1369


(水题)

11-20中午看到这个水题,开开心心随手写了个(算法略),本地测试样例,贼慢……【第一版本时间复杂度太高】

换方法(欧拉筛法素数表【表打错了】)…答案不对了……【第二版本是算法错误】

后来又写了两种(两种素数判定)……【第三、第四版本均为算法错误】

内心:MMP

当时已经貌似已经有人以很快的时间,20ms左右过了这道题了,还在想要不要进行getchar优化读入。。。我到写这份解题报告的时候都不知道他们用的什么算法……(╯‵□′)╯︵┻━┻
现在知道了:遍历[1,floor(sqrt(n))) 左闭右开,单独判定sqrt(n) [不知道我当时是怎么写错的的……

但是11-21下午,在上无聊的英语课的时候,在反思素数表是不是打错了的时候,萌生了这样一个想法。

当遍历至某一个数i 的时候,把i之后,数值为 n * i ( n ∈ N+) 的因数全部+1。有点筛法的味道,但我感觉严格意义上讲不能称之为筛法。

易证,此算法所需运算次数为

时间复杂度为O(n*ln(n))

晚上试了试,果然AC了,而且奇快无比,用的还是cin。


 


贴代码,贴代码

//0ms
#include <iostream>
#include <cstring>
#include <cstdio> 

using namespace std;

const int N = 70000, SIZE = N * 1.1;

int a[SIZE], b[SIZE];


int main(){
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	int d = 0;
	for(int i = 1; i < N; i++){
		b[i] = b[i-1];
		for(int x = 1; i * x <= N; x++){
			a[i*x] ++;
		}
		if(a[i]==4)
			d++, b[i]++;
	}
	
	int w, e;
	while(cin>>w>>e){
		cout<<b[e]-b[w-1]<<endl;
	}
	return 0;
}

此代码可以微调以后直接AC 1369

埃拉托斯特尼筛法是O(nlglgn)的时间复杂度,我这个想法是萌生于筛法,那么我希望可以把它优化到欧拉筛法的速度O(n),所以,我又想到了几处优化:

  1. i = 1 时的操作可以删除,最终判定改为 if(a[i]==3) [无卵用]
  2. 1. 的基础上,当 x = 1时的操作可以删除,最终判定改为 if(a[i]==2) [无卵用] 综合1, 2,即“不再考虑一个数本身和1这两个因数”。
  3. 1, 2的基础上(也可以独立),在b[i] = b[i-1] 后,当a[i]>2时,continue[优化效果最显著]

对于上面第三条的证明:当一个数α为4因子数时,以他为因数的数β 一定包含α的所有因数,且这些因数均小于α,已经在之前的操作中加入到β的因子数中去了。

然而这TM还是O(nlnn)

//12ms
#include <iostream>
#include <cstring>
#include <cstdio> 

using namespace std;

const int N = 700000, SIZE = N * 1.1;

int a[SIZE], b[SIZE];


int main(){
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	int d = 0;
	for(int i = 2; i < N; i++){
		b[i] = b[i-1];
		if(a[i]>2) continue;
		for(int x = 2; i * x <= N; x++){
			a[i*x] ++;
		}
		if(a[i]==2)
			d++, b[i]++;
	}
	
	int w, e;
	while(cin>>w>>e){
		cout<<b[e]-b[w-1]<<endl;
	}
	return 0;
}

多次试验验证:此优化可将常数减小一半


11-23号更新:

昨天晚上与S.和N.的交流中得到了一点启发,那天中午我的算法之一,用素数表的判定方法,只是有几个细节的错误。今天中午到今天下午有了灵感,今天晚上最终写好。
最终优化时间:4ms 时间复杂度O(n),空间复杂度 O(n) 

此方法在数据范围为7000w时,仍然能有820ms-920ms左右的表现。恐怖的速度。
尚未评估当查询量很大时的效率,因为查询的速度不是O(1),所以可能在查询量特别大的时候速度不佳

曾经我一度认为第二版优化代码的时间复杂度为O(n),但经过实际检验和数学验证得出结论:仍然是O(nlnn),举个例子:对于n=30030=2*3*5*7*11*13, 有6个数对此数进行了筛选,这明显是浪费时间的。

使用的方法:欧拉筛法求素数表、欧拉函数φ(两者同时求出)

易证:一个四因子数必定为两个不同素数的乘积或一个素数的立方。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define _c(x) memset(x, 0, sizeof(x))

using namespace std;

const int N = 700000;

int primelist[70000], phi[N];
bool check[N];  // == 0 -> prime

int getv(int T) {
	int ans = phi[(int)cbrt(T)];
	for(int i = 0, c, d, t = T/2; primelist[i]<=t; i++) {
		c = phi[primelist[i]]; d = phi[T/primelist[i]];
		if( d <= c ) break;
		ans += d - c;
	}
	return ans;
}

int main() {
	_c(primelist);
	_c(phi);
	_c(check);
	for(int i = 2, x = 0; i<N/2; i++) {
		phi[i] = phi[i-1];
		if(!check[i])
			primelist[x++] = i,
			phi[i]++;
		for(int j = 0; j < x && i * primelist[j] < N; j++) {
			check[i * primelist[j]] = 1;
			if(i % primelist[j] == 0)
				break;
		}
	}
	int a, b;
	while(cin>>a>>b) {
		cout<<getv(b)-getv(a-1)<<endl;
	}
	return 0;
}

 


Log:

2017-11-21 第一版

2017-11-23 午 加入P1369 及优化的代码

2017-11-23 晚 加入P1369 进一步优化代码

CC BY-NC-SA 4.0 TSOJ 1362&1369 四因子数 解题报告 by J. Chen is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.