階乘因式分解（一）（南陽oj56）

階乘因式分解（一）（南陽oj56）

階乘因式分解（一）

描述

給定兩個數m,n,其中m是一個素數。

將n（0<=n<=10000）的階乘分解質因數，求其中有多少個m。

輸入

第一行是一個整數s（0 隨後的s行, 每行有兩個整數n，m。

輸出

輸出m的個數。

樣例輸入

2
100 5
16 2

樣例輸出

24
15

來源

網絡

上傳者

苗棟棟

#include
int main()
{
	int i,j,test,n,m,t,sum;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&n,&m);
		for(i=m,sum=0;i<=n;i+=m)
		{
			for(j=1,t=i;!(t%m);j++)
			{
				t/=m;
				sum++;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}