J - 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.

Input：

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.

Output：

For each test case, output the number of days ago the Republic became independent, modulo 1,000,000,007, one per line.

Sample Input：

4
9348095
6297540
0

Sample Output：

4
177582252
644064736

题解：

1、打素数表
2、计算 n! 中含有素因子个数，如果为奇数就保留这个素因子的乘积，以便最后相除
3、求出除法结果

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 10000005
#define INF 0x3f3f3f3f
int v[maxn], prime[maxn][2];//prime[i][0]是记录质数p，prime[i][1]是记录质数p的个数
int m = 0;
ll jiecheng[maxn];//阶乘打表
void xianxing(int n)//线性筛
{
	for (int i = 2; i <= n; i++)
	{
		if (v[i] == 0)
		{
			v[i] = i;
			prime[++m][0] = i;
		}
		for (int j = 1; j <= m; j++)
		{
			if (prime[j][0] > v[i] || prime[j][0] * i > n)
			{
				break;
			}
			v[i*prime[j][0]] = prime[j][0];
		}
	}
}
ll quickpow(ll a, ll b, ll c)
{
	if (b == 0)return 1;
	if (b == 1)return a;
	else
	{
		if (b % 2 == 0)
		{
			ll t = quickpow(a, b / 2, c);
			return t * t%c;
		}
		else
		{
			ll t = quickpow(a, b / 2, c);
			t = t * t%c;
			return t * a%c;
		}
	}
}
int main()
{
	xianxing(10000000);
	int n;
	ll temp = 1;//记录阶乘的
	jiecheng[1] = 1;
	for (int i = 2; i <= 10000000; i++)//阶乘打表
	{
		temp = temp * i%mod;
		jiecheng[i] = temp;
	}
	while (~scanf("%d", &n) && n)
	{
		ll gg = 1;
		ll result = 1;
		for (int i = 1; i <= m; i++)//记录质数p的个数的表初始化
		{
			if (prime[i][0] > n)break;
			prime[i][1] = 0;
		}
		ll temp2 = 1;
		for (int i = 1; i <= m; i++)//利用n!中p（p为质数）的个数为  求和n/（p的k次方） ，k为1到正无穷，将n！质因数分解
		{
			gg = 1;
			if (prime[i][0] > n)break;//质数都比输入的大了，没必要去判断了，直接break
			for (int j = 1; j <= 1000000; j++)
			{
				gg *= prime[i][0];
				if (n / gg == 0)break;//后面全为0，加了也没意义，直接break
				prime[i][1] += int(n / gg);
			}
			if (prime[i][1] % 2 == 1)temp2 = temp2 * prime[i][0] % mod;//记录奇因子的乘积
		}
		//D mod p = [(n!) mod p]∗[(奇数个因子的乘积)mod p]p−2
		result = (jiecheng[n] * quickpow(temp2, mod - 2, mod)) % mod;
		printf("%lld\n", result);
	}
}