快速幂

py秒杀

q=int(input())
for i in range(q):
    a,b,p=map(int,input().split())
    print(int(pow(a,b,p)))

您的查询是计算模幂运算 \( a^b \mod p \)，即计算 \( a \) 的 \( b \) 次幂后对 \( p \) 取模的结果。这是一个在数论、密码学（如RSA算法）和计算机科学中常见的操作。由于您没有提供具体的 \( a \)、\( b \) 和 \( p \) 的值，我将先解释一般方法，然后给出一个示例。如果您有具体的数值，请提供它们，我可以为您计算。 ### 1. **什么是模幂运算？** - \( a^b \mod p \) 表示先计算 \( a \) 的 \( b \) 次方（\( a^b \)），然后除以 \( p \) 取余数。 - 直接计算 \( a^b \) 可能非常巨大（尤其当 \( b \) 很大时），导致计算溢出或效率低下。因此，通常使用高效算法（如快速幂算法）直接在模 \( p \) 下计算，避免大数问题。 ### 2. **高效算法：快速幂（平方-乘算法）** 快速幂算法通过将指数 \( b \) 分解为二进制形式，并重复进行平方和乘法操作，将时间复杂度优化到 \( O(\log b) \)。以下是算法的步骤（伪代码）： ```plaintext 函数 mod_exp(a, b, p): 初始化 res = 1 // 结果变量 a = a % p // 先取模，确保a在[0, p-1]范围内 while b > 0: 如果 b 是奇数: res = (res * a) % p // 乘法操作 a = (a * a) % p // 平方操作 b = b // 2 // 右移一位（整数除法） 返回 res ``` **算法说明**： - **初始化**：将结果 `res` 设为 1，并先对 \( a \) 取模 \( p \)（确保 \( a < p \))。 - **循环处理指数 \( b \)**： - 如果 \( b \) 是奇数，将 `res` 与 \( a \) 相乘后取模 \( p \)。 - 将 \( a \) 平方后取模 \( p \)。 - 将 \( b \) 除以 2（整数除法），相当于右移一位。 - **终止**：当 \( b = 0 \) 时，返回 `res`。 - **注意**：如果 \( p \) 是质数且 \( a \) 不被 \( p \) 整除，可以使用费马小定理（\( a^{p-1} \equiv 1 \mod p \)）进一步优化，即先计算 \( b' = b \mod (p-1) \)，然后求 \( a^{b'} \mod p \)。但这需要额外条件。 ### 3. **示例计算** 假设要计算 \( 2^{10} \mod 11 \)（这里 \( a = 2 \), \( b = 10 \), \( p = 11 \))。使用快速幂算法逐步演示： | 步骤 | b | b 的奇偶性 | res（更新前） | a（更新前） | 操作（根据奇偶性） | res（更新后） | a（更新后） | b 更新（b // 2） | |------|------|------------|---------------|-------------|---------------------|---------------|-------------|------------------| | 0 | 10 | 偶数 | 1 | 2 | 先平方 a：a = (2 * 2) mod 11 = 4 | 1 | 4 | 10 // 2 = 5 | | 1 | 5 | 奇数 | 1 | 4 | res = (1 * 4) mod 11 = 4；然后平方 a：a = (4 * 4) mod 11 = 16 mod 11 = 5 | 4 | 5 | 5 // 2 = 2 | | 2 | 2 | 偶数 | 4 | 5 | 先平方 a：a = (5 * 5) mod 11 = 25 mod 11 = 3 | 4 | 3 | 2 // 2 = 1 | | 3 | 1 | 奇数 | 4 | 3 | res = (4 * 3) mod 11 = 12 mod 11 = 1；然后平方 a：a = (3 * 3) mod 11 = 9 | 1 | 9 | 1 // 2 = 0 | | 结束 | 0 | — | — | — | 循环终止 | — | — | — | **结果**：\( 2^{10} \mod 11 = 1 \)（验证：\( 2^{10} = 1024 \)，\( 1024 \div 11 = 93 \times 11 = 1023 \)，余数为 1）。 ### 4. **注意事项** - **输入要求**：\( a \) 和 \( b \) 应为整数，\( p \) 应为正整数（通常 \( p > 1 \))。如果 \( p = 1 \)，结果总是 0（因为任何数模 1 余 0）。 - **负数处理**：如果 \( a \) 为负数，可先转换为等价的正数（如 \( a \mod p \) 在范围 \([0, p-1]\) 内）。 - **大数问题**：当 \( b \) 很大时（如超过 1000 位），快速幂算法是必需的。直接计算 \( a^b \) 会溢出。 - **优化**：如果 \( p \) 是质数，且 \( a \) 与 \( p \) 互质（即 \( \gcd(a, p) = 1 \))，可先用费马小定理简化指数：计算 \( b' = b \mod (p-1) \)，然后求 \( a^{b'} \mod p \)。但这不适用于所有情况。 - **代码实现**：以下是 Python 代码示例，您可以直接运行： ```python def mod_exp(a, b, p): res = 1 a = a % p while b > 0: if b % 2 == 1: # b 是奇数 res = (res * a) % p a = (a * a) % p b = b // 2 return res # 示例：计算 2^10 mod 11 print(mod_exp(2, 10, 11)) # 输出：1 ``` ### 5. **请提供具体值** 如果您有具体的 \( a \)、\( b \) 和 \( p \)（例如 \( a = 3 \), \( b = 100 \), \( p = 17 \))，请告诉我，我可以为您计算并给出逐步过程。或者，如果您有其他相关问题（如理论解释、应用场景），我也很乐意帮助！

方法一：快速幂

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        while (in.hasNextInt()) {
                        // 注意，用例中的数较大，用int会溢出
            long a = in.nextInt();
            long b = in.nextInt();
            long p = in.nextInt();
            System.out.println(quickPow(a,b,p));
        }
    }

    // 非递归
    public static long quickPow(long num, long pow, long p) {
        long result = 1l;
        while (pow > 0) {
            if((pow&1)>0){
                result = (result*num) % p;
            }
            pow >>= 1;
            num = (num*num) % p;
        }
        return result % p;
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int q = in.nextInt();
        long[][] nums = new long[q][3];
        for(int i = 0;i < q;i++){
            nums[i][0] = in.nextInt();
            nums[i][1] = in.nextInt();
            nums[i][2] = in.nextInt();
        }
        
        // 由公式（a*b）^ c = a^c * b^c
        for(int i = 0;i < q;i++){
           long res = 1;
           while(nums[i][1] > 0){
                if(nums[i][1] % 2 == 1){
                    nums[i][1]--;
                    res = res * nums[i][0] % nums[i][2];
                }
                nums[i][1] /= 2;
                nums[i][0] = nums[i][0] * nums[i][0] % nums[i][2];
           }
           System.out.println(res);
        }
    }
}

package main

import (
   "fmt"
   "math/big"
)

func main() {
   var q int
   var a int
   var b int
   var p int
   fmt.Scanf("%d\n", &q)
   for i := 0; i < q; i++ {
      fmt.Scanf("%d %d %d\n", &a, &b, &p)
      fmt.Println(getMod(a, b, p))
   }
}
func getMod(a int, b int, p int) int {
   if b == 0 {
      return 1 % p
   }
   t := big.NewInt(1)
   A := big.NewInt(int64(a))
   P := big.NewInt(int64(p))
   for b != 0 {
      if b&1 == 1 {
         t = t.Mul(t, A)
      }
      b >>= 1
      A = A.Mul(A, A)
   }
   mod := t.Mod(t, P)
   return int(mod.Int64())
}

q = int(input())
for _ in range(q):
    a,b,p = map(int,input().split())
    result = 1
    a=a%p
    while b:
        if b%2==1:
            result =(result*a)%p
        a=(a**2)%p
        b=b//2

    print(result)

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    let q=await readline();
    while(line=await readline()){
        let [a,b,p]=line.split(" ").map(it=>parseInt(it));
        console.log(pow(a,b,p));
    }
}()

let pow=function(a,b,p){
    if(b==0) return 1;
    if(b%2==0){
        let num=pow(a,b/2,p);
        return num*num%p;
    }else{
        return a*pow(a,b-1,p)%p;
    }
}

#include<stdio.h>
typedef long long ll;
ll mod(ll a,ll b,ll p)
{
   ll sum=1;
    while(b)    
    { 
        
        if(b&1)
       {
         sum=(sum*a)%p;
         b--;
        
       }
        else
        {
           a=(a*a)%p;
             b=b>>1;
            sum=(sum*a)%p;
            b--;
        }
    }
    return sum;
    
}
int main()
{
    ll p=0,a=0,b=0,q=0;
    scanf("%lld\n",&q);
    while(q--)
    {
        scanf("%lld %lld %lld\n",&a,&b,&p);
       
        printf("%lld\n",mod(a,b,p));
     }
    return 0;
    
    
}

能不能用循环节来做啊，我试了下，示例可以过，但是案例过不了，麻了

#include<bits/stdc++.h>
int main()
{
    int n;
    scanf("%d",&n);
    long long a,b,p;
    for(int i=0;i<n;i++)
    {long long sum=1;
        scanf("%lld %lld %lld",&a,&b,&p);
     //a%=p;b%=p;
        while(b>0)
        {
            if(b&1) 
            { sum=sum*a%p;
        } b=b>>1;
            a=a*a%p;
        }
     printf("%lld\n",sum);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q, a, b, p;
int deal(int a, int b, int p) {
    int ans = 1 % p;
    for (; b; b>>=1) {
        if (b & 1) ans = (ll) ans * a % p;
        a = (ll) a * a % p;
    }
    return ans;
}
int main()
{
    cin>>q;
    while (q--) {
        cin>>a>>b>>p;
        cout<<deal(a, b, p)<<endl;
    }
    return 0;
}