結果

問題 No.1580 I like Logarithm！
コンテスト
ユーザー ID 21712
提出日時 2026-05-21 02:40:19
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 823 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,890 ms
コンパイル使用メモリ 281,696 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-21 02:40:34
合計ジャッジ時間 13,040 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

const M = 1e9+7

func main() {
	var a int
	var b string
	Scan(&a,&b)
	x := len(b)-1
	ans := 0
	ap := 1
	for p := 0; p < x; p++ {
		aap := ap*a%M
		cnt := (aap + M-1) + M-ap + 1
		ans += p*cnt%M
		ans %= M
		ap = aap
	}
	bm := 0
	for _, ch := range b {
		bm = bm*a%M + int(ch - '0')
		bm %= M
	}
	ans += x*(bm + M-ap + 1)%M
	ans %= M
	Println(ans)
}

/*
考察

x = floor(log_A(B)) = strlen(B) - 1

p = log_A(A^p)
p+1 = log_A(A^(p+1))
A^p <= v < A^(p+1)
p = floor(log_A(v))
pとなる値vは (A^(p+1) - 1) - A^p + 1 個

xとなる値は B - A^x + 1 個

Σ[p=1...x](A^(p+1)-1 - A^p + 1) + (B - A^x + 1) mod 10^9+7 が答え

xは最大でも10^5
1 <= p < x まで A^p mod 10^9+7 をA倍していく動的計画法で求めて
B mod 10^9+7 をBの上位桁から動的計画法で求めて


*/
0