简要题意:
求 (prod_{i=1}^n prod_{j=1}^i j) 的末尾有几个零。
显然,我们对原式进行修改:
[prod_{i=1}^n prod_{j=1}^i j
]
[=prod_{j=1}^n j cdot (n-j+1)
]
这是因为每个数 (j) 在所有 (geq j) 的阶乘中都被乘了一遍。
下面我们只需要考虑:
末尾零是如何产生的?—— (2 imes 5 = 10).即每一个 (2) 和 (5) 这一组就会给答案产生 (1) 的贡献。
那么, (5) 的个数和 (2) 的个数哪个多呢?
显然, (2) 的个数 不小于 (5) 的个数, 这是因为,你只需比较这两个式子:
[sum_{j=1}^{infty} lfloor{ frac{n}{5^j}
floor}
]
[sum_{j=1}^{infty} lfloor{ frac{n}{2^j}
floor}
]
分子相同,当然分母小的大喽!
所以我们只需要计算 (5) 的个数。
下面我们定义:
[F_n = sum_{j=1}^{infty} lfloor{ frac{n}{5^j}
floor}
]
也就是 (n) 有的 (5) 的个数。
那么对于每个 (5 imes i) 即 (5) 的倍数,它们会对答案产生的贡献是:
[F_{5 imes i} cdot (n+1-5 imes i)
]
这是因为,我们上面的那个变形。还记得吗?
[prod_{i=1}^n prod_{j=1}^i j
]
[=prod_{j=1}^n j cdot (n-j+1)
]
只需要算单点的贡献即可。
时间复杂度为: (O(frac{n}{5} {log}_5 n) = O(n log n))
如果你觉得是 (O(n log n)) 会妥妥的超时,那你错了。
在不忽略任何常数的情况下:
[O(frac{10^8}{5} {log}_5 10^8) = 12 imes (2 imes 10^7) = 2.4 imes 10^8
]
你可能觉得这个时间复杂度还是有点危险?
确实,这里有 ({log}_5 n) 的更优算法,但这里不再提及。
这可能是因为洛谷的评测机比较快吧……
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
ll n,ans=0;
inline int five(ll n) { //计算5的个数
int s=0;
while(n%5==0)
s++,n/=5;
return s;
}
int main(){
n=read();
for(int i=1;i<=n/5;i++) {
ans+=five(5*i)*(n+1-5*i);
} printf("%lld
",ans);
return 0;
}