n!素因子p的幂 swjtuOJ 2090【数论】-白红宇

n!素因子p的幂 swjtuOJ 2090【数论】

阅读量：6484 次

发布时间：2019-06-23

本文共 1169 字，大约阅读时间需要 3 分钟。

原文地址：（感谢作者）

素因子分解写的非常好！

数论一道好题：给以两个大整数n,s（n<=10^18，s<=10^12）,试找到最大的整数k使得n! % s^k ==0

(1)首先对S进行素因子分解，复杂度O(logN),用map存储，得到所有素因子以及素因子的幂

(2)对于每一个素因子p，计算对应的n!中素因子p的幂(复杂度O(logn))，两者相除取所有p幂的最小值就是对应的最大整数k,总的时间复杂度为O(logs·logn)

　　❤求n!素因子p的幂要用累除法呀( ⊙ o ⊙ )！

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
          6 #include
          
            7 using namespace std; 8 typedef long long ll; 9 const int _max=1e3+10;10 ll n,s,t;11 map
           
             mp;12 map
            
             ::iterator it;13 14 void divide(ll n)15 {16 mp.clear();17 t=0;18 for(ll i=2;i*i<=n;i++){19 if(n%i==0){20 mp[i]++;21 n/=i;22 while(n%i==0){23 mp[i]++;24 n/=i;25 }26 }27 }28 if(n!=1) mp[n]++;29 }30 31 ll judge(ll p){32 ll cnt=0;33 ll now=n;34 while(now){35 cnt+=now/p;36 now/=p;37 }38 return cnt;39 }40 41 ll solve()42 {43 ll ans= 9223372036854775807ll;44 for(it=mp.begin();it!=mp.end();it++){45 ans=min(judge(it->first)/it->second,ans);46 }47 return ans;48 }49 50 int main()51 {52 int T;53 cin>>T;54 while(T--){55 scanf("%lld%lld",&n,&s);56 divide(s);57 printf("%lld\n",solve());58 }59 return 0;60 }