[LightOJ - 1289] LCM from 1 to n

这篇文章以后的更新都会在 https://two-plus-two-make-four.blogspot.com/2020/01/lightoj-1289-lcm-from-1-to-n.html

题意

求 (1, 2, ..., n) 的最小公倍数 (lcm) ，多组测试数据

一些想法

MicroMaker 神犇说是和φ函数有关的一些东西，但是想了半天似乎并没有什么思路
于是就有了一个很暴力的想法
其实还有一个更 naive 的想法，先把质数表跑出来，再预处理出每个质数的次方之类的信息，然后二分查找什么的，都扯到压缩数据了。。。

题解

先用线性筛把 1 ~ 1e8 的所有质数给筛出来
然后考虑这样一个客观事实（来自官方题解）

lcm(1, 2, ..., n + 1) =

• lcm(1, 2, ..., n) * p 这里的 p 是指素数，如果 n + 1 = p ^ k ，那么就得到那样的递推式
• lcm(1, 2, ..., n) 其它情况

有了递推式就好办了

接下来就到了喜闻乐见的 O(n) 过一亿 时间

看到 CSDN 上有人手写 bitset，感觉自带的 bitset 效率也不错啊。。。 STL 依赖症患者

以下是丑陋的代码：

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = 0;

    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = 1;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }

    if (neg)
    {
        x = -x;
    }
}

typedef unsigned int ui;

const ll INF = 1ll << 32;
const int N = 1e8 + 5;
const int U = 1e8;
const int MAX_PRIME_CNT = 6e6 + 5;

int n;
int p[MAX_PRIME_CNT], tot = 0;

ui sum[MAX_PRIME_CNT];
bitset<N> flag;

inline void init()
{
    for (int i = 2; i <= U; i++)
    {
        if (!flag[i])
        {
            p[tot++] = i;
        }

        for (int j = 0; j < tot; j++)
        {
            if (i * p[j] > U)
            {
                break;
            }

            flag[i * p[j]] = 1;

            if (i % p[j] == 0)
            {
                break;
            }
        }
    }

    sum[0] = p[0];
    for (int i = 1; i < tot; i++)
    {
        sum[i] = sum[i - 1] * p[i];
    }
}

inline ui solve(int n)
{
    int x = upper_bound(p, p + tot, n) - p - 1;
    ui ans = sum[x];

    for (int i = 0; i < tot; i++)
    {
        if (p[i] * p[i] > n)
        {
            break;
        }

        int cur = p[i], t = p[i] * p[i];
        while (t / cur == p[i] && t <= n)
        {
            cur *= p[i];
            t *= p[i];
        }
        ans *= cur / p[i];
    }

    return ans;
}

int T;

int main()
{
    init();
    read(T);
    for (int _ = 1; _ <= T; _++)
    {
        read(n);
        printf("Case %d: %lld\n", _, solve(n) % INF);
    }
}