icpc7306 Primorial vs LCM

acm Math

LCM(1 to 2) = (2)
LCM(1 to 3) = (2 3)
LCM(1 to 4) = (2 2 3)
LCM(1 to 5) = (2 2 3 5)
LCM(1 to 6) = (2 2 3 5)
LCM(1 to 7) = (2 2 3 5 7)
LCM(1 to 8) = (2 2 2 3 5 7)

LCM(1 to n) = 每個質數^最大次方 互乘

LCM(1 to n)/prime(1 to n) = 每個質數^(最大次方 - 1)互乘

問題解法: 先把prime找出來, 再列出他們的幕 (不列質數自身, 因為之後要除prime(1 to n))
把他們排一下, 再一直乘

icpc7306.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;

const LL MAXN = 1e14 + 5;
const int MAXF = 1e7 + 5;
const LL MODV = 1000000007;

vector< pair<LL, int> > degrees;
vector<LL> ans;
bool isprime[MAXF];

void add_primes(int a) {
  for(double i = (double)a*a; i < MAXN; i*=a)
    degrees.push_back( make_pair(i, a) );
}

void build_ans() {
  memset(isprime, true, sizeof(isprime));

  isprime[0] = isprime[1] = false;
  degrees.push_back( make_pair(1, 1) );
  for(LL i = 4; i < MAXF; i += 2) {
    isprime[i] = false;
  }
  add_primes(2);
  for(int i = 3; i < MAXF; i += 2)
    if(isprime[i]) {
      add_primes(i);
      for(LL j = i*2; j < MAXF; j += i) {
        isprime[j] = false;
      }
    }

  sort(degrees.begin(), degrees.end());
  ans.push_back(1);
  for(int i = 1; i < degrees.size(); ++i) {
    ans.push_back( (ans[i-1]*degrees[i].second)%MODV );
  }
}

int main() {
  build_ans();

  int N;
  LL val;
  scanf("%d", &N);
  for(int i = 1; i <= N; ++i) {
    scanf("%lld", &val);
    int head = 0, tail = degrees.size()-1, mid;
    while(head < tail) {
      mid = (head+tail+1) >> 1;

      if(degrees[mid].first > val) {
        tail = mid - 1;
      } else {
        head = mid;
      }
    }
    printf("Case %d: %lld\n", i, ans[head]);
  }
  return 0;
}