結果

問題 No.1252 数字根D
コンテスト
ユーザー ID 21712
提出日時 2026-06-01 02:11:32
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 1,763 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,129 ms
コンパイル使用メモリ 283,360 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-06-01 02:11:56
合計ジャッジ時間 19,653 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var t int
	Scan(&t)
	
	for ; t > 0; t-- {
		var d,a,b int
		Scan(&d,&a,&b)
		ans := solve(d,a,b)
		Println(ans)
	}
}

func solve(d, a, b int) int {
	s := nStar(d,a)
	x := b-a
	y := x/(d-1)
	z := x%(d-1)
	ans := s + y*d*(d-1)/2
	if s+z >= d {
		t := s+z-(d-1)
		ans += t*(t+1)/2
		z -= t
	}
	ans += z*s+z*(z+1)/2 
	return ans	
}

/*
考察

N*は 0 以上 d-1 以下の値になると思われる

f(N)は桁和なので
f(N+1) = f(N) + 1
となるかもしれない
これは少し怪しい
桁の繰り上がりが考慮されていない
それに
f(N+d) = f(N) + 1
かもしれない（桁の繰り上がりが考慮されてない）
f(N+d^2) = f(N) + 1
かもしれない（桁の繰り上がりが考慮されてない）
桁の繰り上がりが発生する場合
f(N+1) < f(N)
f(N+d) < f(N)
f(N+d^2) < f(N)
もありうる

脳内でいろいろ考えてたが

おそらくN*は1～d-1で循環してそう

*/

func init() {
	check()
}

func nStar(d, n int) int {
	for n >= d {
		t := 0
		for n > 0 {
			t += n % d
			n /= d
		}
		n = t
	}
	return n
}

func check() {
	for d := 2; d <= 30; d++ {
		p := 0
		for n := 1; n < 1000; n++ {
			p++
			if p >= d {
				p = 1
			}
			x := nStar(d, n)
			if x != p {
				println("d=",d)
				println("n=",n)
				println("p=",p)
				println("x=",x)
				panic("wrong")
			}
		}
	}
	for d := 2; d <= 15; d++ {
		for a := 1; a < 100; a++ {
			for b := a; b < 100; b++ {
				ans := solve(d, a, b)
				expect := 0
				for k := a; k <= b; k++ {
					expect += nStar(d, k)
				}
				if ans != expect {
					println("d=",d)
					println("a=",a)
					println("b=",b)
					println("ans=",ans)
					println("expect=",expect)
					panic("wrong")
				}
			}
		}
	}
	println("OK")
}
0