\(\\\)
\(Description\)
求一个能被\([1,n]\) 内所有数整除的最小数字，并对 \(100000007\) 取模
- \(N\in [1,10^8]\)
\(\\\)
\(Solution\)
一道卡常好题 好吧是我常数太大了
考虑将限制区间内所有数质因数分解，对每一个质因子\(i\)记录下\(t_i\)表示，这个质因子在区间内任意一个数里，出现的最高幂次，那么答案就应该是每个质因子对应的最高幂之积。
质数可以线性筛 注意常数别写丑了 ，考虑如何求每一个质数的最高次幂。考虑将上限\(N\)除掉一次质因数\(p_i\),得到的数就代表原来那些含\(p_i\)的数的个数。于是一直将\(N\)除\(p_i\)至\(0\)，那么合法的除的次数就是最高幂次的指数。
然后我写了个快速幂就\(T\)了......注意到迭代的同时是可以记录这个最高次幂的结果的，所以可以去掉快速幂的\(log\)复杂度虽然只快了几十毫秒依然卡着时限
\(\\\)
\(Code\)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100000010
#define R register
#define mod 100000007ll
using namespace std;
typedef long long ll;
bool vis[N];
int n,prm[N>>3];
inline void init(int n){
for(R int i=2;i<=n;++i){
if(!vis[i]) prm[++prm[0]]=i;
for(R int j=1,k;j<=prm[0]&&(k=prm[j]*i)<=n;++j){
vis[k]=1; if(i%prm[j]==0) break;
}
}
}
inline ll qpow(ll x,ll t){
ll res=1;
while(t){
if(t&1) (res*=x)%=mod;
(x*=x)%=mod; t>>=1;
}
return res;
}
int main(){
scanf("%d",&n); init(n);
R ll tmp,res,ans=1;
for(R int i=1;i<=prm[0];++i){
tmp=(ll)n; res=1;
while(tmp>=prm[i]) (res*=prm[i])%=mod,tmp/=prm[i];
(ans*=res)%=mod;
}
printf("%lld\n",ans);
return 0;
}