锐客网

  1. 首页 > it技术 > >

牛客网Wannafly挑战赛25|牛客网Wannafly挑战赛25 A题

题目大意 题目链接
给你n,p两个数，求n的阶乘中p做为因子出现的个数
分析 如果p为质数的话，很容易求出p出现的次数,但是这道题p可能为合数，由数学知识可以知道任意一个数都可以通过质数相乘来得到，所以我就将p分解为多个质数来相乘，同时求出相应的质数在n的阶乘中出现的次数a，同时我也要求出质数在p中出现的次数b（一个质数可以出现多次），最后的结果就是多个质数的a/b值的最小值。
代码

#include #include #define INF 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int MAX_N=10002; bool prime[MAX_N]; void getprime() { memset(prime,true,sizeof(prime)); prime[0]=false; prime[1]=false; for(int i=2; i>n>>p; ull result=INF; for(int i=1; i<=p; i++) { if(prime[i]&&p%i==0) { int mid=p; int cnt=0; while(mid%i==0) { mid=mid/i; cnt++; } ull res1=number(n,i); res1=res1/cnt; result=min(result,res1); } } cout<

【牛客网Wannafly挑战赛25|牛客网Wannafly挑战赛25 A题】总结
要明白这道题的思维过程，并能举一反三，求类似这样的问题。同时开数组的时候要注意0的个数。如果题目中要多次用到素数，那么就采用打表的方式一次求出所有的素数（埃氏筛选法则）。

    推荐阅读


    上一篇：各个方面的证据告诉我，鸟类就是最好的

    下一篇：（日更挑战第23天）怀念乔丹