本文共 1310 字，大约阅读时间需要 4 分钟。

直接写不好写

考虑$lcm$是取每个数分解质因子后,每种质因子的最高次幂

那我们看,青蛙会把所有只包含一种质因子的数筛掉

那么对于质因子$p$,包含最多幂$p$的数显然是$2p^x<=n$

解出这个$x$就是对$lcm$的贡献

特殊的,$p=2$时,接触$3p^x<=n$的最大$x$

#include 
   
    using namespace std;typedef long long ll;const int mod = 1e9+7;const int maxn = 160000000;bool vis[maxn+10],ok[maxn+10];int prime[maxn],top,n;void make_prime(){
       for(int i=2;i<=maxn;i++)    {
           if( !vis[i] )    prime[++top] = i;        for(int j = 1;i*prime[j]<=maxn;j++)        {
               vis[i*prime[j]] = 1;            if( i%prime[j]==0 )    break;        }    }}int gcd(int a,int b){
    return b==0?a:gcd(b,a%b); }int quick(int x,int n){
       int ans = 1;    for( ; n ; n>>=1,x=1ll*x*x%mod )           if( n&1 )    ans = 1ll*ans*x%mod;       return ans;}int lcm(int a,int b){
    return 1ll*a*b%mod*quick(gcd(a,b),mod-2)%mod; }int main(){
       cin >> n;    make_prime();    int ans = 1;    for(int j=2;j<=top;j++)    {
           ll now = 2*prime[j]; int ci = 0;        while( now<=n )        {
           	ci++; now = now*prime[j]; ans = 1ll*ans*prime[j]%mod;		}    }    //7的话是6     ll now = 3*2;    while( now<=n )    {
       	now = now*2; ans = 1ll*ans*2%mod;	}    if( ans==1 )    cout << "empty";    else    cout << ans;}//如果刚好是素数的次幂,会被筛选掉//
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113577102 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！