23 solutions

  • 8
    @ 2022-3-16 16:29:12

    可以分治,将 ana^n 变成 afracn2×afracn2a^{frac{n}{2}}\times a^{frac{n}{2}},但如果此时 nn 是奇数,则多乘一个 aa

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll a,b,p=1e9+7;
    ll qpow(ll a,ll b,ll p){
    	ll res=1,tmp=a;
    	while(b){
    		if(b&1)res=(res%p*tmp%p)%p;
    		tmp=(tmp*tmp)%p;
    		b>>=1;
    	}
    	return res;
    }
    int main(){
    	cin>>a>>b>>p;
    	cout<<qpow(a,b,p)<<endl;
    	return 0;
    }
    
    • 4
      @ 2023-10-5 10:40:34
      #include<bits/stdc++.h>
      #define ll long long
      using namespace std;
      ll a,b,p=1e9+7;
      ll qpow(ll a,ll b,ll p){
      	ll res=1,tmp=a;
      	while(b){
      		if(b&1)res=(res%p*tmp%p)%p;
      		tmp=(tmp*tmp)%p;
      		b>>=1;
      	}
      	return res;
      }
      int main(){
      	cin>>a>>b>>p;
      	cout<<qpow(a,b,p)<<endl;
      	return 0;
      }
      
      
      • 4
        @ 2022-3-12 10:29:27

        我来水题解了

        一道典型的快速幂模板题。 (这不是废话吗)

        考虑aba^b,我们将bb表示成二进制形式,然后定义一个basebase作为基数,一开始等于aa。从右往左遍历bb的每一位,如果当前位为11则给答案ansans乘上对应的基数basebase,然后将basebase变为其平方。最后ansans就是答案。

        复杂度O(logb)O(logb)

        注意:以上操作实现过程中均要对pp取模。

        代码:

        #include <bits/stdc++.h>
        using namespace std;
        #define int long long
        int a,b,mod;
        int ksm(int x,int p)
        {
            int base=x;
            int ans=1;
            //下面运用了一些位运算小技巧。
            while(p)
            {
                if(p&1)ans=ans*base%mod;
                p>>=1;
                base=base*base%mod;
            }
            return ans%mod;
        }
        signed main()
        {
            cin>>a>>b>>mod;
            cout<<ksm(a,b);
            return 0;
        }
        
        • 4
          @ 2021-11-30 12:48:17

          代码自认为十分好懂

          #include<cstdio>
          using namespace std;
          #define ll long long
          ll cal(ll a, ll b, ll p)
          {
              ll ans = 1 % p;
              for (; b; b >>= 1)//个人码风原因,也可使用while循环额外加b >>= 1
              {
                  if (b & 1)
                      ans = ans * a % p;//及时取模防止爆掉
                  a = a * a % p;//及时取模防止爆掉
              }
              return ans;
          }
          int main()
          {
          	ll a, b, p;
          	scanf("%lld %lld %lld", &a, &b, &p);
          	printf("%lld", cal(a, b, p));
              return 0;
          }
          
          • 4
            @ 2021-10-6 10:36:04

            快速幂 - OI Wiki (oi-wiki.org)

            #include<bits/stdc++.h>
            using namespace std;
              
            int main()
            {
                unsigned long long a,b,mode ;
                cin>>a>>b>>mode;
                int sum=1;
                a =a%mode;
                while(b>0)
            	{
                    if (b%2==1)
            		{
            			sum =(sum*a)%mode;
            		}
                    b /= 2;
                    a = (a * a) % mode;
            
               }
            cout<<sum;
            }
            
            • 4
              @ 2021-10-3 13:16:15

              快速幂的基本原理是简单的:欲计算 aba^b 的值,只需计算 ab/2a^{b/2} 的值即可。

              在数论题当中,时常涉及到乘法的取模运算。这里用到一个原理:

              (a×b)modp=[(amodp)×(bmodp)]modp(a\times b)\,\bmod p= [(a\,\bmod p)\times(b\,\bmod p)]\,\bmod p

              int solve(int a,int b){
              	if(b==0) return 1;
              	if(b==1) return a%p;
              	if(b%2==0){
              		int tmp = solve(a,b>>1); //必须预存tmp的值,否则程序的效率与普通乘幂无异
              		return (tmp*tmp)%p;
              	}else{
              		int tmp = solve(a,b>>1);
              		return (tmp*tmp*(solve(a,1))%p)%p;
              	}
              }
              
              • 4
                @ 2021-9-14 20:46:51

                知识点:快速幂

                递归公式(分治思想):

                xy=(xy2)2xy2y2x^y=(x^{\lfloor\frac{y}{2}\rfloor})^2\cdot x^{y-2\cdot{\lfloor\frac{y}{2}\rfloor}},而终止条件为 y=0y=0,此时 xy=1x^y=1

                即:

                xy={(xy2)2(2y)(xy12)2x(2y)1(y=0)x^y=\begin{cases} (x^{\frac{y}{2}})^2\qquad(2\mid y)\\ (x^{\frac{y-1}{2}})^2\cdot x(2\nmid y)\\ 1\qquad\qquad(y=0) \end{cases}

                代码如下:

                int qpow(int a,int b){//即a^b
                    if(b==0) return 1;//终止条件
                    else if(b%2==0){
                        int k=qpow(a,b/2);
                        return k*k%MOD;
                    }
                    else{
                        int k=qpow(a,b/2);
                        return k*k%MOD*a%MOD;
                    }
                    //分治思想
                }
                

                我曾经写过一个及其精彩的错误代码:

                int qpow(int a,int b){//即a^b
                    if(b==0) return 1;//终止条件
                    else if(b%2==0){
                        return qpow(a,b/2)*qpow(a,b/2)%MOD;
                    }
                    else{
                        return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;
                    }
                    //分治思想
                }
                

                本代码有什么问题?(设问的修辞手法

                答:这里。

                return qpow(a,b/2)*qpow(a,b/2)%MOD;
                

                以及:

                return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;
                

                这里相当于计算了两次qpow(a,b/2)

                所以需要乘 bbaa

                那么此“快速”幂的复杂度为 O(b)O(b)

                真正的快速幂的复杂度约为 O(logb)O(\log{b})

                用上面的那个即可通关。

                • 3
                  @ 2023-11-11 18:06:10

                  板子题,直接放代码:

                  #include<bits/stdc++.h>
                  #define int long long
                  using namespace std;
                  int a,b,m;
                  int power(int a,int b,int m){
                      long long ans=1;
                      while(b){
                          if(b&1){
                              ans=ans*a%m;
                          }
                          a=a*a%m;
                          b>>=1;
                      }
                      return ans;
                  }
                  signed main(){
                     cin>>a>>b>>m;
                     cout<<power(a,b,m);
                  }
                  
                  • 3
                    @ 2023-3-25 17:32:39
                    #include<bits/stdc++.h>
                    #define ll long long
                    using namespace std;
                    ll a,b,p=1e9+7;
                    ll qpow(ll a,ll b,ll p){
                    	ll res=1,tmp=a;
                    	while(b){
                    		if(b&1)res=(res%p*tmp%p)%p;
                    		tmp=(tmp*tmp)%p;
                    		b>>=1;
                    	}
                    	return res;
                    }
                    int main(){
                    	cin>>a>>b>>p;
                    	cout<<qpow(a,b,p)<<endl;
                    	return 0;
                    }
                    
                    
                    • 3
                      @ 2022-10-15 20:49:49

                      题目大意

                      给出 aa, bb, pp。求 abmodpa^b\bmod p

                      做法

                      注意到 b231b\leq 2^{31} ,所以我们最好可以有一个O(logn)\mathit{O(logn)}的算法来求快速幂。那么,分治,它来了。

                      详细介绍

                      接下来,就是思考如何用分治解决这个题目。当我们求 abmodpa^b\bmod p 时,我们可以把原式子分为两个 ab/2modpa^{b/2}\bmod p 的积, 如果 b1(mod2)b\equiv1\pmod{2} ,还得乘上一个 aa 才能等于 abmodpa^b\bmod p 。这样递归下去,我们就能实现分而治之了。

                      代码

                      #include <bits/stdc++.h>
                      #define int long long
                      using namespace std;
                      int x,y,p;
                      int pw(int x,int y,int p){
                      	int re=1;
                      	while(y){
                      		if(y&1) re=re*x%p;//y&1是判y的奇偶性
                      		x=x*x%p;
                      		y>>=1;//等同于y/=2
                      	}
                      	return re;
                      } 
                      signed main(){
                      	cin>>x>>y>>p;
                      	cout<<pw(x,y,p)<<endl;
                      	return 0;
                      }
                      

                      完结,撒花!!!

                      • 3
                        @ 2022-7-21 21:19:08
                        #include<iostream>
                        using namespace std;
                        int main (){
                            int a, b, p;
                            int ans = 1;
                            scanf("%d%d%d", &a, &b, &p);
                            while(b){
                                if(b & 1)
                                    ans = (long long) ans * a % p;
                                a = (long long) a * a % p;
                                b >>= 1;
                            }
                            printf("%d", ans % p);
                            return 0;
                        }
                        
                        • 3
                          @ 2022-6-19 12:40:23

                          此题解是 JuliaRoadmap 项目的一部分

                          题解里很多人用递归的方法,这里不再阐述。注意到可以对bb 进行二进制拆分,例如对于12=(1100)212=(1100)_2,只需从左到右循环即可

                          题目中限定 b<231b<2^{31},使用以下代码

                          function main()
                              a=parse(Int, readuntil(stdin,' '))
                              b=parse(Int, readuntil(stdin,' '))
                              p=parse(Int, readline())
                              a%=p
                              ans=1
                              for i in 31:-1:0
                                  sign=(b>>i)&1 # 位运算技巧
                                  if sign==0
                                      ans=ans*ans%p
                                  else
                                      ans=(ans*ans%p)*a%p
                                  end
                              end
                              print(ans)
                          end
                          main()
                          

                          评测结果492~614ms

                          • 2
                            @ 2023-9-17 22:50:10

                            自认为代码很通俗

                            首先,直接算是肯定不行的,我们要一步一步来

                            相关知识请看 OI Wiki

                            #include<bits/stdc++.h>
                            using namespace std;
                            int main(){
                                long long b,p,k;
                                cin >> b >> p >> k;
                                long long ans = 1;
                                while (p != 0){
                                    if(p % 2 !=0)ans = ans * b % k;
                                    p /= 2;
                                    b = b * b % k;
                                }
                                cout << ans;
                            }
                            
                            • 2
                              @ 2023-8-12 15:12:01

                              核心代码一行的快速幂:

                              #include <bits/stdc++.h>
                              using namespace std;
                              typedef long long ll;
                              ll a, b, p;
                              ll power (ll a, ll b, ll p) {
                              	return b == 0? 1: (b & 1? a: 1) * power (a * a % p, b >> 1, p) % p;
                              }
                              int main () {
                                  scanf ("%lld%lld%lld", &a, &b, &p);
                                  printf ("%lld", power (a, b, p));
                                  return 0;
                              }
                              

                              压行(164B)!

                              #import<iostream>
                              typedef long long L;L a,b,p;L P(L a,L b,L p){return b?(b&1?a:1)*P(a*a%p,b/2,p)%p:1;}int main(){std::cin>>a>>b>>p;std::cout<<P(a,b,p);return 0;}
                              

                              顺便找了一个不递归的压了压(182B):

                              #import<iostream>
                              typedef long long L;L a,b,p;L P(L a,L b,L p){L S=1;while(b){if(b&1)S=S*a%p;a=a*a%p;b/=2;}return ans;}int main(){std::cin>>a>>b>>p;std::cout<<P(a,b,p);return 0;}
                              

                              可以发现,前者代码短一点。

                              (喂喂我这个大码量人为什么要玩 Code Golf 啊

                              • 2
                                @ 2023-8-11 15:37:15

                                Hydro H1032【模板】快速幂 & 洛谷 P1226 题解

                                #include<iostream>
                                using namespace std;
                                long long a,b,p,q,w;
                                int loop(long long x,long long y)
                                {
                                    if(y==0)
                                    {
                                        return 1;
                                    }
                                    long long res=1;
                                    while(y)
                                    {
                                        if(y&1)
                                        {
                                            res=res*x%p;  /*需要%*/
                                        } 
                                        x=x*x%p;  /*需要%*/
                                //      cout<<x<<endl;
                                        y>>=1;
                                    } 
                                    return res;
                                }
                                
                                int main()
                                {
                                    cin>>a>>b>>p;
                                    q=loop(a,b);
                                    w=q % p;
                                    cout<<w<<endl;
                                }
                                
                                • 2
                                  @ 2023-7-11 8:44:50

                                  整点最短解。以下是利用 python3 完成的一个很短的写法(37 B):

                                  print(pow(*map(int,input().split())))
                                  
                                  • @ 2023-8-27 9:30:46

                                    Python自带高精度,是一个简单的语言

                                • 2
                                  @ 2023-1-21 12:53:38

                                  其实很简单。。。

                                  #include<iostream>
                                  using namespace std;
                                  #define int long long
                                  int a,b,p;
                                  int power(int a,int b,int p){
                                  	int ans=1;
                                  	while(b){
                                  		if(b&1==1)ans=ans*a%p;
                                  		a=a*a%p;
                                  		b>>=1;
                                  	}return ans;
                                  }
                                  signed main(){
                                  	cin>>a>>b>>p;
                                  	cout<<power(a,b,p);return 0;
                                  }
                                  
                                  • 2
                                    @ 2022-10-23 11:23:50

                                    使用分治思想,每次将指数 nn 减半,再平方。但如果 nn 是技术,则要再乘 aa

                                    #include<bits/stdc++.h>
                                    using namespace std;
                                    typedef long long ll;
                                    const int INF=0x3f3f3f3f;
                                    inline ll read()
                                    {
                                    	ll x=0,f=1;char ch=getchar();
                                    	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
                                    	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
                                    	return x*f;
                                    }
                                    ll quickpow(ll a,ll b,ll m){
                                    	if(b==0)  return 1;
                                    	ll tmp=quickpow(a,b/2,m)%m;
                                    	ll ans=tmp*tmp%m;
                                    	if(b&1)  ans=ans*a%m;
                                    	return ans; 
                                    }
                                    int main(){
                                    	ll a,b,p;
                                    	a=read(),b=read(),p=read();
                                    	cout<<quickpow(a,b,p);
                                    	return 0;
                                    }
                                    
                                    
                                    • 1
                                      @ 2022-8-22 20:14:26

                                      学完初一数学自然就会了。

                                      #include<bits/stdc++.h>
                                      #define ll long long
                                      using namespace std;
                                      long long a,b,s,ans;
                                      ll p(ll a,ll k)
                                      {
                                      	ll res=1; 
                                      	while(k)
                                      	{
                                      		if(k&1) 
                                      		{
                                      		   res=(ll)res*a%s;
                                      		}
                                      		k>>=1;
                                      		a=(ll)a*a%s; 
                                      	}
                                      	return res;
                                      }
                                      int main()
                                      {
                                      	cin>>a>>b>>s;
                                      	cout<<p(a,b)%s;
                                      }
                                      
                                      • 1
                                        @ 2022-5-29 15:53:04
                                        a=input().split#输入,切片
                                        print(str(pow(int(a[0]),int(a[1]),int(a[2]))))#pow函数
                                        

                                        Information

                                        ID
                                        171
                                        Time
                                        1000ms
                                        Memory
                                        256MiB
                                        Difficulty
                                        2
                                        Tags
                                        # Submissions
                                        808
                                        Accepted
                                        278
                                        Uploaded By