西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛 E 呼兰河传

Description

沿着河边看一看清冷的夏夜，耳机里是AR的《呼兰河传》。AR的呼兰河并非一条河，而是一个故乡小城的生活日记。静谧的童年，孩子看世界的眼光，花开鸟飞间的自由，塑造了一方那个时代中少有的美好。现在，你需要回答以下问题，才可倾听这首《呼兰河传》带来的温柔，试试吧。给你n个数，选择一些数，使得LCM最大，输出LCM的最大值并对1e9+9取模。
LCM：最小公倍数

Solution

直接做LCM的话在取模的时候会出现错误，不能直接求n个数字的LCM
转化为质因数分解，对于每个质因子取最高次幂的结果就是最终的答案
例如 分别是
最终答案就是
注意一些优化细节，提前做一下素数筛，以及在质因数分解的时候不用跑满所有质因子
然后是数组不必开1e6, 边读边分解就完事了

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int mod = 1e9 + 9;
const int N = 2e5 + 5;
int prime[N], p[N], cnt, mp[N];
void init() {
  int len = sqrt(1e5);
  for(int i = 2; i <= len; i++) {
    if(!prime[i]) {
      p[++cnt] = i;
      mp[i] = cnt;
      for(ll j = 2 * i; j <= len; j += i) {
        prime[j] = 1;
      }
    }
  }
}
int ans[N];
ll qpow(ll a, ll b) {
  ll res = 1;
  while(b) {
    if(b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n;
  init();
  cin >> n;
  for(int i = 1; i <= n; i++) {
    int pre;
    cin >> pre;
    for(int j = 1; j <= cnt && pre >= p[j]; j++) {
      int cur = 0;
      if(pre % p[j] == 0) {
        while(pre % p[j] == 0) {
          ++cur;
          pre /= p[j];
        } 
      }
      ans[j] = max(ans[j], cur);
    }
    if(pre > 1) {
      int j = 0;
      if(!mp[pre]) {
        p[++cnt] = pre;
        mp[pre] = cnt;
        j = cnt;
      }
      else j = mp[pre];
      ans[j] = max(1, ans[j]); 
    }
  }
  ll res = 1;
  for(int i = 1; i <= cnt; i++) {
    res *= qpow(p[i], ans[i]);
    res %= mod;
  }
  cout << res << "\n";
  return 0;
}