解題區/解題區 - UVa

UVa 12396 - Remoteland

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

求 N! 的因數中最大的完全平方數。

Sample Input

1
2
3
4
4
9348095
6297540
0

Sample Output

1
2
3
4
177582252
644064736

Solution

對 N! 做因數分解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h> 
#include <algorithm>
using namespace std;
#define maxL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[1048576], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i; 
        }
    }
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while(y) {
        if(y&1)
            ret *= x, ret %= mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
}
int main() {
    sieve();
    int n;
    const long long mod = 1000000007LL;
    while(scanf("%d", &n) == 1 && n) {
        long long ret = 1;
        for(int i = 0; i < Pt; i++) {
            long long p = P[i], cnt = 0;
            while(p <= n)
                cnt += n / p, p *= P[i];
            if(cnt < 2)	break;
            ret *= mpow(P[i], cnt/2*2, mod);
            ret %= mod;
        } 
        printf("%lld\n", ret);
    }
    return 0;
}