本文主要是介绍SWERC 2011 / HDU 4196 Remoteland (数论想法题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Remoteland
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 262144/131072 K (Java/Others)
http://acm.hdu.edu.cn/showproblem.php?pid=4196
思路：
显然取n!是最大的，但这不一定是一个完全平方数，需要把多余的部分除掉。
可以利用勒让德定理很快处理出n!所有素因子的指数，偶数保留，奇数减1，即可保证这些素因子最后乘积为完全平方数，也就是用n!除以所有指数为奇数的素因子的乘积。注意由于有取模运算，所以不能直接除。——那怎么办？
可以利用勒让德定理很快处理出n!所有素因子的指数，偶数保留，奇数减1，即可保证这些素因子最后乘积为完全平方数，也就是用n!除以所有指数为奇数的素因子的乘积。注意由于有取模运算，所以不能直接除。——那怎么办？
换个思路，先把n!除以<=n的所有质数，再乘上指数为偶数的质数！
（先乘再除转化为先除再乘！）
完整代码：
/*1718ms,90976KB*/#include<cstdio>
#include<cmath>
const long long mod = 1000000007;
const int mx = 10000001;
const int sqrtmx = (int)sqrt((double)mx);long long fac[mx] = {1, 1};
bool vis[mx];
int prime[664580], cnt;void init()
{for (int i = 2; i < mx; ++i){fac[i] = fac[i - 1];if (!vis[i]){prime[cnt++] = i;if (i <= sqrtmx)for (int j = i * i; j < mx; j += i)vis[j] = true;}else fac[i] = (fac[i] * i) % mod;}
}int main()
{init();int n;while (scanf("%d", &n), n){long long res = fac[n];for (int i = 0; i < cnt && prime[i] <= (n >> 1); ++i){int r = 0, tmp = n;while (tmp) r += (tmp /= prime[i]);if ((r & 1) == 0) res = (res * prime[i]) % mod;}printf("%lld\n", res);}return 0;
}
这篇关于SWERC 2011 / HDU 4196 Remoteland (数论想法题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
