寒假安排
Time Limit: 2000/1000MS (Java/Others)
Memory Limit: 128000/64000KB (Java/Others)
Submit Statistic 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
没错，又是一道关于素数的数学问题，ACdream上这种题目比例实在是高的可怕~~~偏偏这种题目一看就有头绪让人手痒有AC它的冲动。
求方案数很简单，n(n-1)……(n-m+1)共m次，当然你不用求出来，你只要知道n和n-m+1就好了。这些数字是连起来的，是解题的关键。然后处理k，末尾几个0相信每个人都能想到就是答案能够整除几个k，整除几个k，就是整除几组k的素因数。所以你要先把k的素因数求出来，log(n)的复杂度，格式如下：比如20：2个2和1个5. 对于一个素因数，何以求得可以整除几次呢，由于方案数公式是连续的数字，相信你会求。然后你要接着求它能整除几次2个素因数，3个素因数。。。。加起来的总和除以素因数在k中的个数，就是方案数能整除几个该素因数。所有素因数的可除数最小值即能整除几组k的素因数。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<iomanip>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std;
ll n,m,k,numl,numr,res,bi,n2;
bool su[70000];
struct node{ll x,bi,ge,sum;
}dui[70000];
vector<ll> b;
void setup(){int i,j;MM(su,1); b.clear();for(i=2;i<=65536;i++){for(j=i+i;j<=65536;j+=i) su[j]=false;if(su[i]) b.push_back(i); }
}
ll cal(ll x){ll res;ll yu=numr%x,fi,la=numl-numl%x;if(!yu) fi=numr;else fi=x-yu+numr;if(la>=fi) res=((la-fi)/x+1);else res=0;return res;
}
int main()
{int i,j,T;setup();scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&n,&m,&k);res=0; numl=n; numr=n-m+1; n2=0;for(i=0;i<b.size();i++){if(k==1 || b[i]*b[i]>k) break;if(k%b[i]==0){n2++; dui[n2].x=dui[n2].bi=b[i]; dui[n2].ge=1; k/=b[i]; dui[n2].sum=0;while(k%b[i]==0){dui[n2].ge++; k/=b[i]; } } }if(k!=1){n2++; dui[n2].x=dui[n2].bi=k; dui[n2].ge=1; dui[n2].sum=0; } ll tmp; i=1;while(i<=n2){tmp=cal(dui[i].x);if(tmp==0){i+=1;continue;} else {dui[i].sum+=tmp; dui[i].x*=dui[i].bi; }}res=dui[1].sum/dui[1].ge; for(i=2;i<=n2;i++){res=min(res,dui[i].sum/dui[i].ge);if(res==0) break;} cout<<res<<'\n';}return 0;
}