慕容琳的后花园
慕容琳的后花园
洛谷#CF300E#Empire Strikes Back

Empire Strikes Back

给定k个数a1,a2…ak
求一个数n,使n!是a1!a2!…ak!的倍数

解法

这是一道数论好题啊
手推了一个小时,然后没开longlong挂掉了,有点自闭
看到数据范围,k是1e6,a是1e7
阶乘的处理方式肯定是计算质因数,这里我们用了欧拉筛,这样可以每次精确定位到质因子(这是我想出来最快的方法了,大佬别怼我qwq)
计算质因数的复杂度大概就是max(a)×平均质因子个数,反正有5秒,卡一卡就过去了
上面只是简单的数论运用,接下来才是让人自闭的地方=-=
我们既然求出了n!需要含有的所有质因子,那么对于每一种质因子求能满足的最小n,在这些n里面取max
那么这个n怎么求呢,我们知道要求n!中某个质因子m的数量,需要用n除以m的1~p次方
现在将这个式子乘以m的p次方后展开,当n等于m的p次方时,我们可以得到这个质因子的数量x=(m^(p)-1)/(m-1)
对于每一段l~r的区间,i(l<=i<=r)不是x的任意次方且r-l+1是x的p次方时,该区间的累乘和中质因子x的数量是一个定量(自己思考一下为什么qwq)
那么就可以贪心来求解上面的问题了,对于每个质因子m的数量k,我们可以从大到小枚举p(0<=p<=log_p(k)),然后就能找到所需要求的n
对于这个贪心,复杂度也是log,所以总复杂度大概是(大常数(质因子数量)×max(a)+m(质数数量,远小于max(a))log(m))

ac代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000010],cnt=0,v[10000010],prime[1000010],mp[10000010],g[10000010],tot[1000010];
int maxx,res,sum,x;
void init(){for(int i=1;i<=n;i++)scanf("%lld",&a[i]),mp[a[i]]++,maxx=max(maxx,1ll*a[i]);}
void get_prime()
{
    for(int i=2;i<=maxx;i++)
    {
        if(!v[i])v[i]=i,prime[++cnt]=i,g[i]=cnt;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]>v[i]||prime[j]>maxx/i)break;
            v[i*prime[j]]=prime[j];
        }
    }
}
//欧拉筛
void calc(int k){while(k!=1)tot[g[v[k]]]+=res,k/=v[k];}
//用欧拉筛分解质因数
void work(){for(int i=1;i<=maxx;i++){calc(i);res-=mp[i];}}
//通过mp的优化可以不用对每个阶乘处理,注意!!!
int calcx(int k)
{
    res=0,sum=prime[k];
    while(sum<tot[k])sum*=prime[k];
    while(tot[k])x=(sum-1)/(prime[k]-1),res+=tot[k]/x*sum,tot[k]%=x,sum/=prime[k];
    return res;
}
//计算出最小的阶乘满足质因子的数量
void get_ans(){for(int i=1;i<=cnt;i++)maxx=max(maxx,calcx(i));}
signed main()
{
    freopen("strike.in","r",stdin),freopen("strike.out","w",stdout);
    scanf("%lld",&n),res=n,init(),get_prime(),work(),maxx=1,get_ans(),printf("%lld\n",maxx);
    return 0;
}
赞赏
首页      洛谷      洛谷#CF300E#Empire Strikes Back
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/b5524d7953a2d9e8b016b3a59801dc6c?s=80&d=monsterid&r=g
    LightningUZ

    博主是女孩子?!

    9月前回复
  • https://secure.gravatar.com/avatar/b5524d7953a2d9e8b016b3a59801dc6c?s=80&d=monsterid&r=g
    LightningUZ

    而且还特别东方?!

    9月前回复
  • https://secure.gravatar.com/avatar/b5524d7953a2d9e8b016b3a59801dc6c?s=80&d=monsterid&r=g
    LightningUZ

    博主tql%%%

    9月前回复

慕容琳的后花园

洛谷#CF300E#Empire Strikes Back
Empire Strikes Back 给定k个数a1,a2...ak 求一个数n,使n!是a1!a2!...ak!的倍数 解法 这是一道数论好题啊 手推了一个小时,然后没开longlong挂掉了,有点自闭 看到数据范围,k是1e6,…
扫描二维码继续阅读
2019-05-06
功能