题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

时间复杂度

O(logk)

参考文献

Golang 代码

package main

import (
    "fmt"
    "bufio"
    "os"
    "strings"
    "strconv"
)

func main() {
    n := 0
    fmt.Scanln(&n)
    reader := bufio.NewReader(os.Stdin)
    for n > 0 {
        line := readline(reader)
        a, k, p := line[0], line[1], line[2]
        res := qmi(a, k, p)
        fmt.Println(res)
        n--
    }    
}

func qmi(a, k, p int) int {
    res := 1
    for k > 0 {
        if k & 1 == 1 {
            res = res * a % p
        }
        k >>= 1
        a = a * a % p
    }
    return res
}

func readline(reader *bufio.Reader) []int {
    strline, _ := reader.ReadString('\n')
    params := strings.Fields(strline)
    line := make([]int, len(params))
    for i, elem := range params {
        line[i], _ = strconv.Atoi(elem)
    }
    return line
}