結果

問題 No.793 うし数列 2
コンテスト
ユーザー tsuchinaga
提出日時 2019-05-10 09:10:38
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,271 bytes
コンパイル時間 11,352 ms
コンパイル使用メモリ 239,064 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-02 00:55:42
合計ジャッジ時間 11,387 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
	}
}
0