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 을 먼저!< = 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
", res);
	}
	return 0;
}