2015
05-23

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

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.

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.

4
9348095
6297540
0

4
177582252
644064736

#include <stdio.h>

long long ans[10000001];
char comp[10000001];
int primes[700000];

int main() {
ans[0] = ans[1] = 1;
int l = 0;
for (int i=2; i<=10000000; i++) {
ans[i] = ans[i-1];
if (!comp[i]) {
primes[l++] = i;
if (i < 4000)
for (int j=i*i; j<=10000000; j+=i)
comp[j] = 1;
}
else
ans[i] = (ans[i] * i) % 1000000007;
}
int n;
while(scanf("%d", &n) == 1 && n) {
long long res = ans[n];
for (int i=0; i<l && primes[i] <= n/2; ++i) {
int cnt = 0;
int tn = n;
do {
tn /= primes[i];
cnt += tn;
}while(tn >= primes[i]);
if (cnt % 2 == 0)
res = (res * primes[i]) % 1000000007;
}
printf("%lld\n", res);
}
return 0;
}

1. 当我看到官方给的程序的时候我傻了，只有做过这个题，并不断超时的人才能体会代码是那么的优美，其他的言语都是多余的所以这就是你不写分析，不写注释的原因吗[笑泪]