ACdream 1084 寒假安排（数论（k进制末位的0的数目+n!中v因子个数））

ACdream 1084 寒假安排（数论（k进制末位的0的数目+n!中v因子个数））

题目：​​Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

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

分析：

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

ll go(ll n, ll v){

ll ans = 0;

ll tmp = v;

while(n>=tmp){  //如果 tmp>n,另一个因子会小于1.

ans += n/tmp;

tmp*=v;

}

return ans;

}

或：

1*2*3*4*…*n = p^(n/p)*(1*2*,,,,*(n/p))*[原因子中不能被p整除的书的乘积]  那么 f[n][p] = n/p + f[n/p][p]，就可以通过递归的方法求出了。

LL getnum(int n,int p){

if(n

return n/p+getnum(n/p,p);

}

A(n,m)=n!/(n-m)!=n(n-1)(n-2)*……*(n-m+1)  取k的因子最小的数目即是结果。 用素因子分解： int prime[maxn],top1=0; bool notprime[maxn]; void getprime(){     for(int i=2;i<=maxn;i++){         if(!notprime[i])prime[top1++]=i;         for(int j=0;j

关于k的因子最小的数目 的解释：A(n,m)转换成k进制有多少个零相当于它能连续被几个k整除，因此将k进行素因子分解，例如20=2^2*5，阶乘有几套k的素因子就有几个零。A(n,m)=n!/(n-m)!=n(n-1)(n-2)*……*(n-m+1) “A(n,m)除以k的素因子，等于n!除以k的素因子减去(n-m)!除k以的素因子”--》s[i]=getsum(n,fac[i])-getsum(n-m,fac[i]); 最后查看有几套：loop: minm=min(s[i]/fac[i],minm) 整个循环的结果就是"几套k的素因子"。 现在先见一个例子：

#include #include#include#includeusing namespace std;typedef long long LL;LL getzero(LL n,LL v){ if(n1){ sta[top]=m; pnum[top++]++; }}LL pnum1[maxn],pnum2[maxn];LL sys[maxn],stp;void turn(LL m,LL v){ stp=0; while(m>0){ sys[stp++]=m%v; m/=v; }}LL factorial(int m){ if(m==2) return 2; return m*factorial(m-1);}LL facA(int n,int m){ LL ans=1,aq=n-m; while(n>aq){ ans*=n; n--; } return ans;}int main(){ freopen("cout.txt","w",stdout); LL n,m,k; while(cin>>n>>m>>k){ fenjie(k); memset(pnum1,0,sizeof(pnum1)); memset(pnum2,0,sizeof(pnum2)); cout<<"n!= "<=0;i--)cout<=0;i--)cout<=0;i--)cout<=0;i--)cout<>t; while(t--){ scanf("%d%d%d",&n,&m,&k); fenjie(k); memset(pn,0,sizeof(pn)); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。