HDU 4196 Remoteland

Description

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,n]里选择一些数，使乘积是完全平方数的最大值。

可以直接预处理出10000000的全部答案。

考虑g[i]表示[1,i]的答案，考虑g[i]的递推。

加入当前的数字i，把i拆成素数因子的乘积，g[i]=g[i-1]*i

考虑奇数个的素数因子，如果该素数在g[i-1]里存在，那么从g[i]中除去，

如果不存在，g[i]乘上这个素数。

这样显然可以保证，每次加入的数字都被统计了，并且剩下了的数字都是素数，此时答案是最大的。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define inone(x) scanf("%d", &x)
#define intwo(x,y) scanf("%d%d", &x, &y)
using namespace std;
const int N = 1e7+5;
const int mod=1e9+7;
int n;
int f[N],p[680000],g[N],c[680000],t;
int inv[680000];

int get(int x,int y)
{
    int res=1;
    for (;y;y>>=1)
    {
        if (y&1) res=1LL*res*x%mod;
        x=1LL*x*x%mod;
    }
    return res;
}

void init()
{
    g[1]=1;
    rep(i,2,N-1)
    {
        if (!f[i]) {p[++t]=i; f[i]=t; inv[t]=get(i,mod-2);}
        for (int j=1;j<=t&&i*p[j]<N;j++)
        {
            f[i*p[j]]=j;
            if (i%p[j]==0) break;
        }
        g[i]=1LL*g[i-1]*i%mod;
        for (int j=i;j>1;j/=p[f[j]])
        {
            if (c[f[j]]) g[i]=1LL*g[i]*p[f[j]]%mod;
            else g[i]=1LL*g[i]*inv[f[j]]%mod;
            c[f[j]]^=1;
        }
    }
    //printf("%d",t);
}

int main()
{
    init();
    while(scanf("%d",&n)&&n)
    {
        printf("%d\n",g[n]);
    }
    return 0;
}