题解 | C.idol!!

题目

求$1!!\cdot 2!!\cdot 3!!\cdot \mathrm{.}\mathrm{.}\mathrm{.}\cdot N!!1!!\backslash cdot2!!\backslash cdot3!!\backslash cdot...\backslash cdot\; N!!$的中0的个数。

输入

11

输出

5

思路

​ 显然在统计阶乘末尾 0的时候，5的数目会远少于 2 的数目，因而本质等价于统计含 5 因子的个数——枚举 k，统计有多少个数会是$5^{k}5^k$ 的倍数，对所有 k求和。 ​ 对于奇数的双阶乘之积，如$1!!\cdot 3!!\cdot 5!!\cdot 7!!\cdot 9!!\cdot 11!!\cdot 13!!\cdot 15!!\mathrm{.}\mathrm{.}\mathrm{.}2t+1!!1!!\backslash cdot\; 3!!\backslash cdot\; 5!!\backslash cdot\; 7!!\backslash cdot\; 9!!\backslash cdot\; 11!!\backslash cdot\; 13!!\backslash cdot\; 15!!...2t+1!!$,可以发现1~3可以分为一组，他们中因子5的个数均为0,可以忽略，5~13可以分为1组，他们每个数都有1个因子5，共有5个。从15!!开始，每个双阶乘有2个因子5，共有10个因子5。即15~23可以分为一组，这两组可构成一个首项为5，公差为10的等差数列。

但是到25!!开始,每个双阶乘有4个因子5，不再是像上次一样每次加1个了，那么这是为什么呢？可以发现在之前的数据中，从5开始每5个数就会有一个能整除5的数，5—>15—>25，但到25时就多了2个因子5，这是因为25就是5的整次幂，那么115—>125也类似，会在原基础上增加3个因子5。总结可知，当遍历到5的整次幂时，因子5会增加多个。

那么上述等差数列就用不了了吗？既然从25时，等差数列被打破，原因是在25时多了1个因子5，那么就把它分为3+1就可以重新生成等差数列了。

第一个非零项为5，共有$n(n=(N+1)\mathrm{/}2)n(n=(N+1)/2)$个数据项，每5个数据一组，共有$cn{t}_1=(n-2)\mathrm{/}5\mathrm{组}cnt\_1=(n-2)/5组$，其数列和为$su{m}_1=5\ast (1+cn{t}_1)\ast cn{t}_1\mathrm{/}2sum\_1=5*(1+cnt\_1)*cnt\_1/2$。剩余$cn{t}_2=(n-2)\mathrm{\%}5cnt\_2=(n-2)\backslash \%5$个数据项，剩余的数据项是大于$cn{t}_{1}cnt\_1$的，但与上述一样进行分割，所以剩余项的和$su{m}_2=cn{t}_2\ast (cn{t}_1+1)sum\_2=cnt\_2*(cnt\_1+1)$。设最终答案为$ansans$，那么一次遍历下来$ans=su{m}_1+su{m}_{2}ans=sum\_1+sum\_2$。经过上次计算，剩余的数据项含有因子5的个数如图：

此时似乎又恢复到了第一张图的情景了，可以看到现在第一个非零项为25，且为1，为什么第一项是25呢？因为在25时因子5发生了突增多加了1个5，但此时一组有多少个呢？25个，因为25~73都是1，到75时，与65不同的是他又多了1个因子5，外加25时多加的一个因子5，总共多加了2个因子5，所以经过一次计算后，还剩2个因子5。那么下面同上述步骤一样，先计算总数组，共$nn$个数据项，有$(23+1)\mathrm{/}2=12(23+1)/2=12$个数据项有0个因子5。所以要计算的数据项为$(n-12)(n-12)$项，每项25个，共有$cn{t}_1=(n-12)\mathrm{/}25cnt\_1=(n-12)/25$组，所以$su{m}_1=25\ast (1+cn{t}_1)\ast cn{t}_1\mathrm{/}2sum\_1=25*(1+cnt\_1)*cnt\_1/2$。剩余$cn{t}_2=(n-12)\mathrm{\%}25cnt\_2=(n-12)\backslash \%25$个数据项,剩余的数据项按$cn{t}_1+1cnt\_1+1$计算,所以剩余项的和$su{m}_2=cn{t}_2\ast (cn{t}_1+1)sum\_2=cnt\_2*(cnt\_1+1)$。设最终答案为$ansans$，那么一次遍历下来$ans=ans+su{m}_1+su{m}_{2}ans=ans+sum\_1+sum\_2$。

那么第三次计算每组应该是125个，其中到数据项123之前剩余因子5都是0，那么组数就知道了，同样的等差数列求和。

总结一下，上述变量可以表示为：

计算奇数的代码

int128 slove(LL n) {
	int128 ans=0;
	for(int128 zero=1,w=1; ;) {
		w*=5;//每组个数 
		zero=(w-1)/2;//剩余项为0的个数 
		if(zero>n) break;
		int128 cnt1=(n-zero)/w;//组数 
		int128 cnt2=(n-zero)%w;//余数 
		ans+=w*(1+cnt1)*cnt1/2;//等差数列和 sum1
		ans+=(1+cnt1)*cnt2;//余项和 sum2
	}
	return ans;
}

对于偶数也是如此

唯一变化的是，突增的位置不是25，而是50，因为偶数的话双阶乘到达不了25，同理125也到达不了，只能到达包含因子25的数据项50，也就是25的2倍，才会进行突增，进行一次计算后第一个非0项为50，所以其原理与奇数一样，唯一改变的是非0项的个数每次改变与奇数是不同，因此只要该变计算非0想个数那块的代码即可。即zero=w-1。

对应偶数代码

int128 slove(LL n) {
	int128 ans=0;
	for(int128 zero=1,w=1; ;) {
		w*=5;//每组个数 
		zero=w-1;//剩余项为0的个数 
		if(zero>n) break;
		int128 cnt1=(n-zero)/w;//组数 
		int128 cnt2=(n-zero)%w;//余数 
		ans+=w*(1+cnt1)*cnt1/2;//等差数列和 sum1
		ans+=(1+cnt1)*cnt2;//余项和 sum2
	}
	return ans;
}

综合代码为

#include <bits/stdc++.h>

using namespace std;

using int128=__int128_t;
using LL=long long;

void print(int128 x) {
	if(!x) return;
	print(x/10);
	putchar(x%10+'0');
}

int128 slove(LL n,int k) {	//k表示传入的n是否表示偶数的个数,1:偶数，0:奇数
	int128 ans=0;
	for(int128 zero=1,w=1; ;) {
		w*=5;//每组个数 
		zero=k?w-1:(w-1)/2;//剩余项为0的个数 
		if(zero>=n) break;
		int128 cnt1=(n-zero)/w;//组数 
		int128 cnt2=(n-zero)%w;//余数 
		ans+=w*(1+cnt1)*cnt1/2;//等差数列和 sum1
		ans+=(1+cnt1)*cnt2;//余项和 sum2
	}
	return ans;
}

int main() {
	LL n;
	cin>>n;
	int128 ans=0;
	ans+=slove(n/2,1);//偶数
	ans+=slove((n+1)/2,0); //奇数
	if(!ans) printf("0");
	else  print(ans);
	return 0;
}