【完全平方数】

题目描述

一个数如果是另一个整数的完全平方,那么我们就称这个数为完全平方数(Pefect Sqaure),也称平方数。
小A认为所有的平方数都是很perfect的。
于是他给了小B一个任务:用任意个不大于 n 的不同的正整数相乘得到完全平方数,并且小A希望这个平方数越大越好。
请你帮助小B告诉小A满足题意的最大的完全平方数。

输入格式

输入文件仅 1 行,一个数 n 。

输出格式

输出仅 1 行,一个数表示答案。
由于答案可以很大,所以请输出答案对 100000007 取模后的结果。

样例数据 1

输入

7

输出

144

样例数据 2

输入

9

输出

5184

备注

【样例1解释】
144=2×3×4×6,是 12 的完全平方。

【样例2解释】
5184=3×4×6×8×9,是72的完全平方。

【数据范围】
对于 20% 的数据,0<n≤100;
对于 50% 的数据,0<n≤5,000;
对于 70% 的数据,0<n≤100,000;
对于 100% 的数据,0<n≤5,000,000。

首先把1~10每个数的阶乘算一下,看看可以分出几个质数,在看每个质数可以乘多少次,之后选出现次数为偶数次的质数相乘即可,因为数据很大所以要快速幂!

下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*