#345979 (Go) No.793 うし数列 2

• 問題: No.793 うし数列 2
• ユーザー: tsuchinaga
• 提出日時: 2019-05-10 09:10:38
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,271 bytes
• コンパイル時間: 10,787 ms
• コンパイル使用メモリ: 211,308 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-14 17:50:40
• 合計ジャッジ時間: 11,832 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	1 ms; 4,376 KB
testcase_09	AC	2 ms; 4,380 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	1 ms; 4,376 KB
testcase_12	AC	1 ms; 4,380 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	1 ms; 4,376 KB
testcase_15	AC	2 ms; 4,376 KB
testcase_16	AC	1 ms; 4,376 KB
testcase_17	AC	1 ms; 4,380 KB
testcase_18	AC	1 ms; 4,376 KB
testcase_19	AC	1 ms; 4,376 KB
testcase_20	AC	1 ms; 4,376 KB
testcase_21	AC	1 ms; 4,376 KB
testcase_22	AC	2 ms; 4,376 KB

ソースコード

package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	_, _ = fmt.Scan(&n)

	mod := int(math.Pow10(9)) + 7
	fmt.Println(((4*PowMod793(10, n, mod) - 1) * PowMod793(3, mod-2, mod)) % mod)

	//   1 ->   13 は +12
	//  13 ->  133 は +120
	// 133 -> 1333 は +1200
	// 上記のように、各項は初項12、公比10の等比数列の和となっている
	// 等比数列の和の公式は(a * r^n - a)/rとなっており、これに当てはめると(12 * 10^n - 12)/9となる
	// 計算量の多そうな10^nは二分累乗法を使うことでかなり少ない計算回数で実現できる
	// ただし余りを求めたものの外に割り算があって誤差が出る
	// これを掛け算にするために、フェルマーの小定理を使う
	// 1+(12 * 10^n - 12)/9 は (4 * 10^n - 1)/3に変えられる。
	// 3も10^9+7もともに素数なので、a^(p-1)≡1(mod p)が成り立つ
	// 3^(10^9+6)≡1 -> 3^(10^9+5)≡3^-1
	// これで1/3は3^(10^9+5)と表現できる
	// 以上より、(4 * 10^n - 1) * 3^(10^9+5) で答えが出せる
}

func PowMod793(x, n, mod int) int {
	if n <= 1 {
		return x
	} else if n%2 == 1 {
		return (PowMod793(x, n-1, mod) * x) % mod
	} else {
		m := PowMod793(x, n/2, mod)
		return (m * m) % mod
	}
}