首页 > 代码库 > Acdream1084 寒假安排 求n!中v因子个数

Acdream1084 寒假安排 求n!中v因子个数

题目链接:

pid=1084">点击打开链接

寒假安排

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 128000/64000 KB (Java/Others)
SubmitStatistic 

pid=1085" style="color:rgb(85,85,85); text-decoration:none; vertical-align:middle; display:inline-block; margin:2px 3px; padding:2px 10px; border:1px solid rgb(204,204,204); font-weight:bold; font-size:12px; background-color:rgb(255,255,255)">Next Problem

Problem Description

寒假又快要到了。只是对于lzx来说。头疼的事又来了,由于众多的后宫都指望着能和lzx约会呢,lzx得安排好计划才行。

如果lzx的后宫团有n个人。寒假共同拥有m天,而每天仅仅能跟一位后宫MM约会。而且因为后宫数量太过庞大了。而寒假的天数太少,所以lzx在寒假里不会与一个MM约会一次以上。如今lzx想要知道:寒假安排的方案数如果写成k进制。末位会有多少个0。

Input

输入的第一行是一个整数。为数据的组数t(t<=1000)。

每组数据占一行,为3个正整数n、m和k(1<=m<=n<2^31,2<=k<2^31)。意思如上文所述。

Output

对于每组数据,输出一个数,为寒假安排的方案数写成k进制末位的0的数目。

Sample Input

3
10 5 10
10 1 2
10 2 8

Sample Output

1
1
0

Source

Dshawn

Manager

admin

求n!中v因子个数的做法:

技术分享

代码:

ll go(ll x, ll v){
	ll ans = 0;
	ll tmp = v;
	while(x>=tmp){
		ans += x/tmp;
		tmp*=v;
	}
	return ans;
}

然后把k分解质因素。取因子中最小的数量既是0的个数。

#include<stdio.h>
#include<iostream>  
#include<cstdio>  
#include<queue>  
#include<ctype.h>  
#include<cstring>
#include<math.h>
#include<set>
#include<queue>
using namespace std;
#define ll long long
ll n, m, k;
ll Stack[1000], top, Cnt[1000];
void fenjie(){
	top = 0;
	memset(Cnt, 0, sizeof Cnt);
	for(ll i = 2; i*i<=k; i++)if(k%i==0){
		while(k%i==0)Cnt[top]++, k/=i;
		Stack[top++] = i;
	}
	if(k>1){
		Cnt[top]++;
		Stack[top++] = k;
	}
}
ll go(ll x, ll v){
	ll ans = 0;
	ll tmp = v;
	while(x>=tmp){
		ans += x/tmp;
		tmp*=v;
	}
	return ans;
}
ll tmp[1000];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		cin>>n>>m>>k;
		fenjie();
		memset(tmp, 0, sizeof tmp);
		for(ll i = 0; i < top; i++){
			tmp[i] += go(n, Stack[i]);
		}
		for(ll i = 0; i < top; i++){
			tmp[i] -= go(n-m, Stack[i]);
		}
		ll ans = tmp[0]/Cnt[0];
		for(ll i = 1; i < top; i++)
			ans = min(ans, tmp[i]/Cnt[i]);
		cout<<ans<<endl;
	}
	return 0;
}


Acdream1084 寒假安排 求n!中v因子个数