[ Luogu 4626 ] 一道水题 II

\(\\\)

\(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;

}

巴特西

[ Luogu 4626 ] 一道水题 II

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章