题解 P2388 【阶乘之乘】

· · 题解

预备知识:勒让德定理

对于正整数n,在n!的素因子标准分解式中，素数p的最高指数记作Lp,

则Lp=\sum\limits_{k\geq1} {\frac{n}{p^k}}.

代码实现:

ll Legendre(ll x) {while (x) cnt+=x/5,x/=5; return cnt; }

然后我们发现答案是若干个阶乘相乘,所以答案是勒让德定理算出的数值相加.

注意到2的素因子分布远远多于5,直接计算p=5即可

蒟蒻的代码:

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 500010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define db double
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}

ll n,ans,cnt=0;

ll Legendre(ll x) {while (x) cnt+=x/5,x/=5; return cnt; }

int main()
{
    n=r();
    rep(i,1,n) ans=Legendre(i);
    cout<<ans<<endl;
    return 0;
}