階乗因式分解(二)http://acm.nyist.net/JudgeOnline/problem.php?pid=70

846 ワード


階乗因式分解(二)
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
3
 
説明
2つの数n,mが与えられ、ここでmは素数である.
n(0<=n<=2^31)の階乗分解素因数を、その中に何個のmがあるかを求める.
注意:^はべき乗を求める記号です.
 
 
 
入力
最初の行は整数s(0の後のs行で、各行に2つの整数n,mがある.
しゅつりょく
出力mの個数
サンプル入力
3
100 5
16 2
1000000000  13

サンプル出力
24
15
83333329

ソース
[苗棟棟]オリジナル
アップロード者
苗棟
#include
int main()
{
	int s;
	scanf("%d",&s);
	while(s--)
	{
		int i,n,m,a=0,b=0,c=0;
		int count=0;
		scanf("%d %d",&n,&m);
		while(n!=0)
		{
			count+=n/m;
			n=n/m;
		}
		printf("%d
",count); } return 0; }

この問題を解決する原理は簡単です.nの中にいくつかのm、m*m、m*m*mがあるのを見てみましょう. 
転載先:https://www.cnblogs.com/wangyouxuan/p/3268954.html