idol!! 2023牛客暑期多校训练营6 C

登录—专业IT笔试面试备考平台_牛客网

题目大意：·定义n!!等于与n的奇偶性相同的所有小于等于n的数的阶乘之和，问n!!的末尾有多少0

1<=n<=1e18

思路：因为末尾0的来源是2*5，而2的个数明显比5的个数多得多，所以末尾0的个数就等于有多少个5相乘。

首先我们看所有奇数，在n的范围内有cnt1=(n+1)/2个奇数，然后我们观察发现，除了前两个奇数1,3之外，后面每5个数他们的因数中间包含的5的个数是相同的，比如5~13每个奇数都有一个因数5,15~23有两个，而25~33有4个35~43有5个，前两组和后两组5的个数都相差1，而两者之间相差2，这是因为25不仅有因数5，还有因数25额外提供了一个5，那么如果我们先不管额外提供的这个5，那么每一组5的个数都是等差数列，一共有cnt2=(cnt-1)/5组，每组大小s为5，那么总合也就是（1+cnt2）*s*cnt2/2。

然后所有数对应减去他们本次提供的贡献后，可以发现前两组数剩余5的个数都变成了0，下一组变成了25~73的个数为1，75~123的个数为2,125~173的个数为4，也就是新的等差数列的每组大小变成了a*5，其余都不变，所以我们可以从5开始枚举a，直到所有数的贡献都被计算完毕。

对于偶数，唯一的不同就是一开始前四个数的贡献为0，每次求等差数列后，前四组的贡献清零，分两次求奇偶再加起来就好

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;//答案超过了long long 的数据范围
ll read()
{//直接在函数里面实现读字符串操作更简洁ll res = 0;//初始结果赋值0char scan[1005];scanf("%s", scan);for (int i = 0; i < strlen(scan); i++)res *= 10, res += scan[i] - '0';//实现进位return res;//返回__int128类型
}
void print(ll num)
{//递归调用，实现从高位向低位输出if (num > 9)print(num / 10);putchar(num % 10 + '0');
}
int main()
{ll n = read();ll a = 1;ll ans = 0;ll cnt1 = (n + 1) / 2;//奇数的个数while (cnt1>0){a *= 5;//每组大小ll cnt2 = (cnt1 - 2) / a;//组数ll sum1 = (1 + cnt2) * a * cnt2 / 2;//求等差数列和ll mod = (cnt1 - 2) % a;//不在组里的余数sum1 += (cnt2 + 1) * mod;//单独算一下余数ans += sum1;cnt1 -= 2 * a;//维护剩余有攻陷的数的个数}if (ans < 0){//特判cnt=1print(0);return 0;}a = 1;cnt1 = n / 2;//偶数的的个数while (cnt1>0){a *= 5;ll cnt2 = (cnt1 - 4) / a;//前四组贡献为0ll sum1 = (1 + cnt2) * a * cnt2 / 2;ll mod = (cnt1 - 4) % a;sum1 += (cnt2 + 1) * mod;ans += sum1;cnt1 -= 4 * a;}if (ans < 0){//特判cnt1=1,2,3print(0);return 0;}print(ans);return 0;
}