Wannafly挑战赛25 A.因子

传送门

[https://www.nowcoder.com/acm/contest/197/A]

题意

给你n,m,让你求n!里有多少个m

分析

看这个你就懂了

[https://blog.csdn.net/jiangpengna/article/details/38690023]//这里就是怎么统计n!里有多少个质因子i的原理

这题不同的是m不是素数，你把m分解质因子，统计每个质因子在p里的个数

然后每次取最小即可，具体看代码

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,m,p,ans;

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0); cout.tie(0);

	cin>>n>>p;

	ans=1e18;

	for(int i=2;i<=p;i++)

	 if(p%i==0)//挑出p里的质因子i

	{

		m=n;

		ll cnt=0;

		while(m){//统计n!里有多少个质因子 i

			m/=i; cnt+=m;

		}

		ll sum=0;

		while(p%i==0){//统计p里有多少个质因子i,并并把这个因子全部抠出p

			p/=i; sum++;

		}

		ans=min(ans,cnt/sum);//取最小即可

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

Wannafly挑战赛25 A.因子

传送门

题意

分析

代码

最新文章

热门文章