建设一个国外服务器的网站,网站空间到期了,网站内搜索功能怎么做,seo网络运营登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;定义n!!等于与n的奇偶性相同的所有小于等于n的数的阶乘之和#xff0c;问n!!的末尾有多少0
1n1e18
思路#xff1a;因为末尾0的来源是2*5#xff0c;而2的个数明显比5的个数多得多#xff0c;所以末尾…登录—专业IT笔试面试备考平台_牛客网
题目大意·定义n!!等于与n的奇偶性相同的所有小于等于n的数的阶乘之和问n!!的末尾有多少0
1n1e18
思路因为末尾0的来源是2*5而2的个数明显比5的个数多得多所以末尾0的个数就等于有多少个5相乘。
首先我们看所有奇数在n的范围内有cnt1(n1)/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那么总合也就是1cnt2*s*cnt2/2。
然后所有数对应减去他们本次提供的贡献后可以发现前两组数剩余5的个数都变成了0下一组变成了25~73的个数为175~123的个数为2,125~173的个数为4也就是新的等差数列的每组大小变成了a*5其余都不变所以我们可以从5开始枚举a直到所有数的贡献都被计算完毕。
对于偶数唯一的不同就是一开始前四个数的贡献为0每次求等差数列后前四组的贡献清零分两次求奇偶再加起来就好
//#include__msvc_all_public_headers.hpp
#includebits/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 (cnt10){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){//特判cnt1print(0);return 0;}a 1;cnt1 n / 2;//偶数的的个数while (cnt10){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){//特判cnt11,2,3print(0);return 0;}print(ans);return 0;
}
