こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

べき乗の計算 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

まずは以下のようにべき乗を計算して余りを出力する実装をしました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    exp := 1
    for i := 1; i <= n; i++ {
        exp *= 2
    }
    fmt.Println(exp % 1000003)
}

ですがこれだと実行時間エラーになりました。

以下のように、繰り返し二条法を使うことで解決しました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    m := 1000003
    p := 2
    ans := 1
    for 0 < n {
        if n & 1 == 1 {
            ans = ans * p % m
        }
        p = p * p % m
        n >>= 1
    }
    fmt.Println(ans)
}

シフト演算とかしてるのであまり直感的でないので、ちょっとAIと壁打ちしてもう少し理解を深めます。。

ではこれで👍