14332: 【原4332】最小公倍数

题目

题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4332

Description

定义$lcm(a_1,a_2,\dots,a_n) = a_1,a_2,\dots,a_n$的最小公倍数。

现有一个正整数$n$，求最小的正整数$m$使得$m>n$且$lcm(n+1,n+2,\dots,m)=lcm(1,2,\dots,m)$。

Input Format

一行一个数字$n$。

$1 \leq n \leq 10^6$

Output Format

一行一个数字表示答案

Sample Input

5

Sample Output

10

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
bool vis[1000005] = {0};
void init(){
    n = read();
    for (int i = 2; i <= n; ++i){
        if (!vis[i] && 1ll * i * i <= n){
            for (int j = i * i; j <= n; j += i)
                vis[j] = true;
        }
    }
}
void solve(){
    int ans = 0;
    if (n == 1){
        printf("2\n");
        return ;
    }
    for (int i = 2; i <= n; ++i){
        if (!vis[i]){
            int v = i;
            while (1ll * v * i <= 1ll * n) v *= i;
            ans = max(ans, (n / v) * v + v);
            // ceil((n + 1) / v) * v
        }
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}