首页 > ACM题库 > HDU-杭电 > HDU 4196-Remoteland-数论-[解题报告]HOJ
2015
05-23

HDU 4196-Remoteland-数论-[解题报告]HOJ

Remoteland

问题描述 :

In the Republic of Remoteland, the people celebrate their independence day every year. However, as it was a long long time ago, nobody can remember when it was exactly. The only thing people can remember is that today, the number of days elapsed since their independence (D) is a perfect square, and moreover it is the largest possible such number one can form as a product of distinct numbers less than or equal to n.
As the years in Remoteland have 1,000,000,007 days, their citizens just need D modulo 1,000,000,007. Note that they are interested in the largest D, not in the largest D modulo 1,000,000,007.

输入:

Every test case is described by a single line with an integer n, (1<=n<=10,000, 000). The input ends with a line containing 0.

输出:

Every test case is described by a single line with an integer n, (1<=n<=10,000, 000). The input ends with a line containing 0.

样例输入:

4
9348095
6297540
0

样例输出:

4
177582252
644064736

我不是很喜欢弄解题报告这样的东西,所以,我做过的题好多都忘了,就好像没做过。

这个题,难度并不是很难,但是,却是让我有了另一种思考,以前我一直在想,acm考的到底是什么??知识点??不像啊,好多的题目我根本就不是知识点,我根本就没法下手,根本就不可能做出来,我要怎么做才能提高自己的水平呢?在迷茫中我苦苦的做题,毫无进展,如何才能出了那些“没有知识点”的题目??到现在我也没有答案,今天看到的这个题,确实让我眼前一亮,有着里程碑式的意义,故放在这儿。

算法,很大程度上依靠时间复杂度的优化才能拒绝超时的命运,可是却有一些题,他们在规定的时间复杂度内仍不能解决,要进行常数的优化,前一段时间,看了一套uva的题,题目看起来似乎好像会做一样,但是仔细的一看,要么是数据规模高了一个"半个“数量级,要么是思路有着更细致的算法。总之就是,算法要在细节的地方进行大量的优化,或者在细节的地方进行微处理。

说说这个题的题意吧,1–n的n个数中选若干个数相乘,乘积是个平方数,求如何选择,使得这个乘积最大且是平方数。思路其实很简单,就是找出1–n的乘积中某个素数的"个数”,然后如果这个个数是偶数,那么好办,但是如果是奇数,我们就假设在1–n中这个“素数”没选。这样的结果是,所有的素数都是偶次幂,也就是这些偶次幂的乘积是平方数。

但是,注意这儿的n是10^7,当我看完这个题的,想到上面说的这些东西的时候,我说,简单,给我十分钟,我贴上模板,呵呵,太小看题目了,果断超时啊!!

然我我仔细的分析算法,我发现,这个算法最卡时间的地方是素数筛,哎,悲哀的分析,然后果断分析素数筛,哦,筛到5*10^6就可以了,嗯,我是这么觉得的,然后继续处理,果断还是超时,md,我仍然认为这个题超时的原因是素数筛(悲剧),然后我就悲剧的认为这个超时无法解决,如果用当前的思路(悲剧),进入死结。

百度的解题报告中有一个和我的思路相同,但是,给了一个优化,就是快速求幂的时候,相同指数的合并在一起再求幂,这个确实是一个优化,用他的代码1500ms,而我优化之后仍然超时(悲剧),无奈之下,看标称吧,当我看到官方给的程序的时候我傻了,只有做过这个题,并不断超时的人才能体会代码是那么的优美,其他的言语都是多余的,Orz,看代码吧

#include <stdio.h>

long long ans[10000001];
char comp[10000001];
int primes[700000];

int main() {
	ans[0] = ans[1] = 1;
	int l = 0;
	for (int i=2; i<=10000000; i++) {
		ans[i] = ans[i-1];
		if (!comp[i]) {
			primes[l++] = i;
			if (i < 4000)
				for (int j=i*i; j<=10000000; j+=i)
					comp[j] = 1;
		}
		else
			ans[i] = (ans[i] * i) % 1000000007;
	}
	int n;
	while(scanf("%d", &n) == 1 && n) {
		long long res = ans[n];
		for (int i=0; i<l && primes[i] <= n/2; ++i) {
			int cnt = 0;
			int tn = n;
			do {
				tn /= primes[i];
				cnt += tn;
			}while(tn >= primes[i]);
			if (cnt % 2 == 0)
				res = (res * primes[i]) % 1000000007;
		}
		printf("%lld\n", res);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wukonwukon/article/details/7430785


  1. 当我看到官方给的程序的时候我傻了,只有做过这个题,并不断超时的人才能体会代码是那么的优美,其他的言语都是多余的所以这就是你不写分析,不写注释的原因吗[笑泪]