专业的网站开发建设,企业网站成品源码,手机h5网站,设计师装修网文章目录
阶乘的末尾0整除问题 一、阶乘的末尾0IO链接
本题思路#xff1a;由于本题需要求阶乘的末尾0#xff0c;由于我们知道2*510可以得到一个0#xff0c;那么我们就可以找出2的数和5的数#xff0c;但是由于是阶乘#xff0c;所以5的数量肯定是小于2的数量#xf… 文章目录
阶乘的末尾0整除问题 一、阶乘的末尾0IO链接
本题思路由于本题需要求阶乘的末尾0由于我们知道2*510可以得到一个0那么我们就可以找出2的数和5的数但是由于是阶乘所以5的数量肯定是小于2的数量因此我们只需要知道5的数量即可这里只需要算含有5的次幂的数目即可。
#include bits/stdc.hint main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cinn;//这里我们可以知道2和5的乘积能得到0那么我们可以知道某个数的阶乘中2这个质因子的次数肯定大于5这个质因子出现的次数int cnt0;while(n){cntn/5;n/5;}std::coutcntstd::endl;return 0;
}
二、整除问题IO链接 本题思路:我们可以把 a 给拆分成若干个质因子之积然后看下 2 ~ n 中包含多少个对应的质因子就能得出来最多可以整除 a 的多少次方。比如 a 中有质因子p1、p2、p32 ~ n 中有对应的质因子、num1、num2 … 个那 k 的最大值也就是若干个 num 的最小值。
#include bits/stdc.hint n,a;
std::vectorstd::vectorint ans;void divide(int n)
{for(int i2;in/i;i){if(n%i0){int s0;while(n%i0){s;n/i;} ans.push_back({i,s});}}if(n1) ans.push_back({n,1});}int get_p(int n,int p)
{int cnt0;while(n){cntn/p;n/p;}return cnt;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cinna;divide(a);int resINT_MAX;for(int i0;ians.size();i)resstd::min(res,get_p(n,ans[i][0])/ans[i][1]);std::coutresstd::endl;return 0;
}
