我的思路就是分别将n，a进行分解质因数并把幂次存储在两个power数组里，然后按照a的质因数去遍历，计算每个质因数p的“在n中幂次/在a中幂次"的比值，比值中最小的即为k。
机试指南上提供了另一种高效得多的算法，真是相形见绌啊＝皿＝
题目地址：点击打开链接
题目描述：
给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
输入：两个整数n(2<=n<=1000)，a(2<=a<=1000)
输出：一个整数.
样例输入： 6 10 样例输出： 1 来源： 2011年上海交通大学计算机研究生机试真题 答疑：解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-7827-1-1.html
#include <iostream> #include <cmath> using namespace std; int main(){ int n,a,k,temp; bool isPrime[1000]; int prime[200]; int primeSize; int powerN[1000],powerA[1000]; int facA[200]; int facASize; //preprocess for (int i=2;i<1000;i++){ isPrime[i]=true; } primeSize=0; for (int i=2;i<1000;i++){ if (isPrime[i]==true){ prime[primeSize]=i; primeSize++; for (int j=i*i;j<1000;j+=i){ isPrime[j]=false; } } } while (cin>>n>>a){ //initiate for (int i=0;i<1000;i++){ powerN[i]=powerA[i]=0; } facASize=0; //resolve for (int m;n>1;n--){ m=n; for (int i=0;i<primeSize;i++){//resolve n! if (m%prime[i]==0){ do{ powerN[prime[i]]++; m/=prime[i]; } while(m%prime[i]==0); } if (m==1) break; } } for (int i=0;i<primeSize;i++){//resolve a if (a%prime[i]==0){ facA[facASize]=prime[i]; facASize++; do{ powerA[prime[i]]++; a/=prime[i]; } while(a%prime[i]==0); } if (a==1) break; } //calculate k k=powerN[facA[0]]/powerA[facA[0]];//initiate k for (int i=1;i<facASize;i++){//遍历facA数组 i从1开始 temp=powerN[facA[i]]/powerA[facA[i]];//temp记录N中该因数的幂次是A中的几倍 if (temp<k) //若该因数在n!中的幂次与在a中的幂次的比值temp是目前最小的 k=temp; } //output cout<<k<<endl; } return true; }
