30 solutions

  • 15
    @ 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;
}
    • 5
      @ 2021-9-14 20:46:51

      知识点：快速幂

      递归公式（分治思想）：

      $x^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。

      即：

      $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)。

      所以需要乘 bb 次 aa。

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

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

      用上面的那个即可通关。

      • 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;
}
        • 3
          @ 2021-10-3 13:16:15

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

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

          $$(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;
	}
}
          • 2
            @ 2025-9-11 10:07:38

            快速幂模板题

            题目简述：给定数 a,b,pa, b, p 问aa的bb次方对pp取模的结果。

            若是直接连bb次aa的话，对于b特别大（比如题目中 b≤231b \le 2^{31}）的情况会直接超时，直接使用c++的内置函数 pow，会出现乘法溢出的情况，所以我们需要一个更快地平方做法，也就是

            快速幂

            • 二进制取幂，也称平方法。观察上面的式子（先不考虑取模）aba^b，通过中学数学所学的幂运算知识 ab+c=ab⋅aca^{b+c}=a^b·a^c，我们可以知道对于
              ∑i=1kni=b \sum_{i=1}^{k}{n_i} = b
              我们有
              $\prod _{i = 1}^{k}{a^{n_i}} = a^b, n\epsilon {\left \{ 1, 0 \right \} }$
            • 于是乎对于 aba^b 我们可以写成 nn个a2ka^{2^k}相乘法 的形式。
              我们拿OI-wiki上的例子来解释说明一下：
              313=3(1101)2=38⋅34⋅313^{13} = 3^{(1101)_2} = 3^8·3^4·3^1
              因为 (1101)2(1101)_2 转化为 (13)10(13)_{10}的结果可以看做：
              1⋅20+0⋅21+1⋅22+1⋅23=1+0+4+81·2^0+0·2^1+1·2^2+1·2^3 = 1+0+4+8
              故 313=31+0+4+8=38⋅34⋅313^{13}=3^{1+0+4+8}=3^8·3^4·3^1
            • 由于我们做的乘法次数是针对 bb 的二进制数长度的，所以我们最多只需要做 log⁡2b\log _2b 次乘法，时间复杂度就是 O(log⁡2N)O(\log_2N)。

            快速幂代码

            LL KSM(LL a, LL b) {
	LL res = 1;
	while (b > 0) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

            乘法取模

            解决完了幂运算的问题，我们只需要还需要处理对pp取模的问题。

            • 对于整数aa和整数cc和a÷ca\div c的余数pp，也就是说 a≡pmod  ca\equiv {p}\mod{c}，我们有 $a = \left \lfloor \frac{a}{c} \right \rfloor \times c +p$
              aa可以表示为a÷ca \div c向下取整后加上他们的模数
            • 回到问题当中，对于 a×amod  ca \times a \mod c，
              用dd表示 ⌊ac⌋\left \lfloor \frac{a}{c} \right \rfloor
              并把上面式子带入进去后发现 $(a\times a) = (dc + p) * (dc + p) = (d^2c+2dp)c+p^2$
              得出结论(a×a)mod  p=(amod  p)×(amod  p)(a\times a) \mod{p} = (a\mod{p}) \times (a\mod{p})
            • 所以对于题目中对pp取模的操作，我们只需要在进行完乘法前对他进行一次取模并拿取模后的结果相乘

            取模代码

            LL KSM(LL a, LL b) {
	LL res = 1;
	while (b > 0) {
		if (b & 1) res = ((res % p) * (a % p)) % p;
		a = ((a % p) * (a % p)) % p;
		b >>= 1;
	}
	return res % p;
}

            这里要注意：为了防止取模后的数连续相乘结果过大，所以在乘完之后还要再进行一次取模

            完整AC代码

            #include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
LL a, b, p;

LL KSM(LL a, LL b) {
	LL res = 1;
	while (b > 0) {
		if (b & 1) res = ((res % p) * (a % p)) % p;
		a = ((a % p) * (a % p)) % p;
		b >>= 1;
	}
	return res % p;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b >> p;
	cout << KSM(a, b);	
	return 0;
}
            • 2
              @ 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;
}
              • 2
                @ 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;
}
                • 2
                  @ 2022-10-15 20:49:49

                  题目大意

                  给出 aa, bb, pp。求 ab mod pa^b\bmod p。

                  做法

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

                  详细介绍

                  接下来，就是思考如何用分治解决这个题目。当我们求 ab mod pa^b\bmod p 时，我们可以把原式子分为两个 ab/2 mod pa^{b/2}\bmod p 的积, 如果 b≡1(mod2)b\equiv1\pmod{2} ,还得乘上一个 aa 才能等于 ab mod pa^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;
}

                  完结，撒花！！！

                  • 2
                    @ 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;
}
                    • 2
                      @ 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;
}
                      • 1
                        @ 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);
}
                        • 1
                          @ 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-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

                            • 0
                              @ 2025-1-15 15:22:47

                              注释了啊

                              我第一次在这里做的

                              #include <bits/stdc++.h>
using namespace std;
/*
(a+b)%k = (a%k+b%k)%k
(a*b)%k = ((a%k)*(b%k))%k 
*/

//快速幂  (a^x)%p
// a=1231321313
// x=5464646546
// p=12313 

long long a,x,p;

long long f(int k){//a的k次方 %p的结果 
	if(k==0) return 1;
	if(k==1) return a%p;
	long long tmp=f(k/2);
	if(k%2==0){
		return tmp*tmp%p;
	}else{
		return (tmp*tmp%p)*a%p;
	}
}

int main(){
	cin>>a>>x>>p;
    cout<<f(x);
    return 0;
}
                              • -1
                                @ 2024-6-26 20:38:46

                                #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%ptmp%p)%p; tmp=(tmptmp)%p; b>>=1; } return res; } int main(){ cin>>a>>b>>p; cout<<qpow(a,b,p)<<endl; return 0; }

                                • -1
                                  @ 2024-3-13 14:26:57 
                                  #include <bits/stdc++.h>

using namespace std;
#define int __int128
int read()
{
    int x{},w{1};char c= getchar();
    while(c>'9' || c<'0') {if(c == '-') w=-1;c = getchar();}
    while(c<='9' && c>='0') x = (x<<1)+(x<<3)+c-'0',c = getchar();
    return w * x;
}
void write(int x)
{
    if(x < 0) x = -x,putchar('-');
    if(x>9) write(x/10);putchar(x%10+'0');
}
void writeln(int x)
{
    write(x);putchar(10);
}
const int N = 5e5+5;
int f[N],d[N];
int siz[N],son[N];
struct EDGE
{
    int nxt,to;
}e[N<<1];
int ecnt{},head[N];
void add(int u,int v)
{
    e[++ecnt].to = v;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
}
void dfs1(int u,int fa)
{
    siz[u] = 1,f[u] = fa,d[u] = d[fa]+1;
    for(int i{head[u]};i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
int t[N],dfn[N],a[N],o[N],cnt{};
void dfs2(int u,int top)
{
    dfn[u] = ++cnt;
    a[dfn[u]]=o[u];
    t[u] = top;
    if(!son[u]) return;
    dfs2(son[u],top);
    for(int i{head[u]};i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == f[u] || v == son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v)
{
    while(t[u] != t[v])
    {
        if(d[t[u]] < d[t[v]]) u^=v^=u^=v;
        u = f[t[u]];
    }
    return d[u]<d[v] ? u : v;
}
int qp(int a,int b,int p)
{
    int res{1};
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
signed main()
{
    int a = read(),b = read(),p = read();
    writeln(qp(a,b,p));
}
                                  • -1
                                    @ 2024-2-21 9:55:37 
                                    #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b,p;
    cin>>a>>b>>p;
    ll ans=1%p;//这里注意modp，否则p为1过不了
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b=b>>1;
    }
    cout<<ans;
}
                                    • -1
                                      @ 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;
}
                                      • -1
                                        @ 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 啊

                                        • -1
                                          @ 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;
}

                                          【模板】快速幂

                                          Information

                                          ID
                                          171
                                          Time
                                          1000ms
                                          Memory
                                          256MiB
                                          Difficulty
                                          2
                                          Tags
                                          # Submissions
                                          1639
                                          Accepted
                                          489
                                          Uploaded By
                                          1. Language
                                          2. Legacy mode
                                          3. Theme
                                          2. © 2021-2026 Hydro.ac
                                          4. Worker 2, 56ms
                                          5. Hydro v5.0.0-beta.17-40d4c9b-dirty Professional