ACdream 1084 寒假安排(阶乘素因子分解)
题意：将A(n , m)转化成k进制后末尾0的个数。A(n , m)=n!/(n-m)!
这个题数据很大，需要预处理==
而且自己第二天做想偷懒，不分解k，果然wa了T^T
关于不拆k为什么不对：
分析例子 n=9,m=6,k=4 错的结果是2 对的结果是3 拆一下就懂了
然后还是
int getNum(int n,int p){
if(n<p) return 0;
return getNum(n/p,p)+n/p;
}求素因子
if(n<p) return 0;
return getNum(n/p,p)+n/p;
}求素因子
求A(n, m)转化成k进制以后末尾0的个数。对k素因子分解，第i个因子为fac[i]，
第i个因子的指数为num[i],然后再对A(n, m)进行素因子分解，设count[i]
代表fac[i]对应的指数，ans = min{count[i]/num[i]}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
int pri[maxn],cnt;
bool vis[maxn];
int fac[1000],num;
int Count[1000];
int sum[maxn];
void getFactor(int x){
num=0;
memset(Count,0,sizeof(Count));
for(int i=0;i<cnt&&pri[i]*pri[i]<=x;i++){
if(x%pri[i]==0){
fac[num]=pri[i];
while(x%pri[i]==0) Count[num]++,x/=pri[i];
num++;
}
}
if(x>1) fac[num]=x,Count[num++]=1;
}
int getNum(int n,int p){
if(n<p) return 0;
return getNum(n/p,p)+n/p;
}
int main()
{
// freopen("cin.txt","r",stdin);
memset(vis,0,sizeof(vis));
cnt=0;
for(int i=2;i<maxn;i++){
if(!vis[i]){
pri[cnt++]=i;
for(int j=i+i;j<maxn;j+=i) vis[j]=1;
}
}
int t,n,m,k;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
getFactor(k);
int ans = 1000000000;
for(int i=0;i<num;i++){
//cout<<getNum(n,fac[i])<<" "<<getNum(m,fac[i])<<endl;
sum[i]=getNum(n,fac[i])-getNum(n-m,fac[i]);
ans=min(sum[i]/Count[i],ans);
}
printf("%d\n",ans);
}
return 0;
}
