arc110a
大意
给定 \(N\)
求一个 \(x\in [N,10^{13}]\) ，满足任何正整数 \(y\in [2,N]\) ，$y\mid (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^c\mid x\) 且不存在 \(r\in[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