PKU 4043 Remoteland

概要：1～nまでの異なる数をいくつかかけて最大になる平方数作ってね
解法：n!の素因数分解で出てくる指数を考える。偶数ならそれは問題ないし、奇数ならそこだけ1でほか0の数(いわゆる素数)で1回だけ割ればよいので、素因数ごとに独立に計算できる。

Java逃げ。(26360MS)

import java.util.*;
class Main{
	static int mod=1000000007;
	static long pow(int a,int b){
		long ret=1;
		long now=a;
		while(b>0){
			if(b%2==1)ret=ret*now%mod;
			now=now*now%mod;
			b/=2;
		}
		return ret;
	}
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		short prime[]=new short[10000010];
		int plist[]=new int[1000000];
		prime[0]=prime[1]=-1;
		for(int i=2;i<10000010;i++){
			if(prime[i]!=-1){
				prime[i]=1;
				for(int j=i+i;j<10000010;j+=i)prime[j]=-1;
			}
		}
		int s=0;
		for(int i=0;i<10000010;i++)if(prime[i]!=-1){plist[s++]=i;}
		int a;
		
		while(true){
			a=sc.nextInt();
			if(a==0)break;
			long ret=1;
			int b=a;
			int i;
			for(i=0;i<s&&plist[i]*plist[i]<=a;i++){
				int v=0;
				int c=a;
				while(c>0){
					c/=plist[i];
					v+=c;
				}
				if(v%2==1)v--;
				ret=ret*pow(plist[i],v)%mod;
			}
			for(;i<s&&plist[i]<=a/2;i++)ret=ret*pow(plist[i],(a/plist[i])&(~1))%mod;
			System.out.println(ret);
		}
	}
}