階乗因式分解(二)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