Remoteland

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 908    Accepted Submission(s): 332


Problem 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  
Source SWERC 2011  
题意：用不大于n内的所有数组成一个最大的完全平方数 题解：就是把N！这个数的个数为奇数的素因子除掉，于是就是一个求逆模的问题了，逆模可以用快速幂求，也可以用扩展欧几里得 这里有更加详细的题解 http://blog.csdn.net/acm_cxlove/article/details/7422265

#include #include #include #define mod 1000000007 int prime[1000008],flag[10000008],all=0; long long res[10000008],sum; void init() { long long i,j,cc=sqrt(10000001.0); memset(flag,0,sizeof(flag)); res[0]=res[1]=1; for(i=2;i<=cc;i++) { if(flag[i]) continue; for(j=i*i;j<=10000000;j+=i) flag[j]=1; } for(i=2;i<=10000000;i++) { res[i]=(res[i-1]*i)%mod; if(!flag[i]) prime[all++]=i; } } int get_sum(int x,int n) { int ans=0; while(n) { ans+=n/x; n=n/x; } return ans; } int fpow(long long x,long long n) { long long ans=1; while(n) { if(n&1) ans=(ans*x)%mod; n>>=1; x=(x*x)%mod; } return ans; } void exgcd(int a,int b,int *gcd,int *x,int *y) { if(!b){ *gcd=a; *x=1; *y=0; } else{ exgcd(b,a%b,gcd,y,x); *y-=*x*(a/b); } } int get_inverse_model(int tag,int MOD) { //return fpow(tag,MOD-2); int gcd,x,y; exgcd(tag,MOD,&gcd,&x,&y); return (x+MOD)%MOD; } int main() { int i,n,cou; init(); while(scanf("%d",&n),n) { for(sum=1,i=0;i