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;
}