arc110a

arc110a

大意

给定 (N)

求一个 (xin [N,10^{13}]) ，满足任意正整数 (yin [2,N]) ，$ymid (x-1) $

思路

最基本的思路， ((x-1) = N!) ，这是显然满足 (y|(x-1)) 的，但是 (30!approx 10^{32}) 远超 (10^{13}) ，需要想办法减小。

考虑分解质因数，根据唯一分解定理 (x-1) 一定能分解为 (N) 以内的质数的有限次方的乘积。

然后不难发现，若对于质数 (p) ， (p^c leq N) 且 (p^{c+1} > N) ，那么 (p^cmid x) 且不存在 (rin[2,N]) ，使 (p^{c+1}mid r)

所以我们只需要将 (N) 以内的质数的不大于 (N) 的次方乘起来即可。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define ll long long
#define ull unsigned long long
#define cint const int&
#define Pi acos(-1)

const int mod = 998244353;
const int inf_int = 0x7fffffff;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

ull ans=1;
ull n;

int main() {
    cin >> n;
    for(int i=2; i<=n; i++) 
        if(ans % i){
            ull t = i;
            while(t*i<=n) t*=i;
            ans *= t;
        }
    cout << ans+1;
    return 0;
}

-4,15min