【n!素因子p的幂】swjtuOJ 2090
【注：交大的看到这篇文章要学会自己写，不要为了比赛而比赛！~】
题目大意
数论一道好题：给以两个大整数n,s（n<=10^18，s<=10^12）,试找到最大的整数k使得n! % s^k ==0
数论一道不错的题目，很容易想到思路，但是数据会大一点，有可能爆long long ，笔者由于n!素因子p的幂采用累乘法，在10^12左右的一个素数爆掉了，QAQ 所以还是用累除法来的稳妥！
说一下思路(1)首先对S进行素因子分解，复杂度O(logN),用map存储，得到所有素因子以及素因子的幂(2)对于每一个素因子p，计算对应的n!中素因子p的幂(复杂度O(logn))，，两者相除取所有p幂的最小值就是对应的最大整数k,总的时间复杂度为O(logs·logn)
求n!素因子p的幂要用累除法呀( ⊙ o ⊙ )！
参考代码/*====================================*\|*n!素因子p的幂（累除法）*|\*====================================*/;const int _max = 1e3 + 10;ll n,s,t;map<ll,int>mp;map<ll,int>::iterator it;void divide(ll n){//素因子分解 mp.clear(); t = 0; for(ll i = 2; i * i <= n; ++ i){if(n%i==0){mp[i]++;n/=i;while(n%i==0){mp[i]++;n/=i;}} } if(n!=1) mp[n]++;}ll judge(ll p){//n!素因子分解素数p的幂,累除法 ll cnt= 0; ll now = n; while(now){cnt += now/p;now/=p; } return cnt;}ll solve(){ ll ans = 9223372036854775807ll; for(it= mp.begin();it!=mp.end();++it){ans = min(judge(it->first)/it->second,ans); } return ans;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE int T;cin>>T; while(T–){scanf(“%lld%lld”,&n,&s);divide(s);printf(“%lld\n”,solve()); } return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
最大的成功在于最大的付出。
