結果

問題 No.1161 Many Powers
ユーザー ID 21712
提出日時 2026-06-05 19:05:37
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 1,171 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,153 ms
コンパイル使用メモリ 282,140 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2026-06-05 19:05:59
合計ジャッジ時間 19,105 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"

func main() {
	var a,b,c int
	Scan(&a,&b,&c)
	
	ans := solve(a,b,c)
	
	Println(ans)
	
}

func solve(a, b, c int) int {
	bb := NewInt(int64(b))
	cc := NewInt(int64(c))
	sum := 0
	for i := 0; i < min(a, c); i++ {
		aa := NewInt(int64(i+1))
		x := int(new(Int).Exp(aa,bb,cc).Int64())
		sum = (sum + x)%c
	}
	if a/c > 0 {
		sum = sum*(a/c)%c
		for i := 0; i < a%c; i++ {
			aa := NewInt(int64(i+1))
			x := int(new(Int).Exp(aa,bb,cc).Int64())
			sum = (sum + x)%c
		}
	}
	return sum
}

func init() {
	check()
}

func bruteforce(a, b, c int) int {
	sum := 0
	for i := 1; i <= a; i++ {
		pow := 1
		for k := 0; k < b; k++ {
			pow = (pow*i)%c
		}
		sum = (sum+pow)%c
	}
	return sum
}

func check() {
	for a := 1; a < 100; a++ {
		for b := 1; b < 10; b++ {
			for c := 1; c < 20; c++ {
				ans := solve(a,b,c)
				expect := bruteforce(a,b,c)
				if ans != expect {
					println("a=",a)
					println("b=",b)
					println("c=",c)
					println("ans=",ans)
					println("expect=",expect)
					panic("wrong")
				}
			}
		}
	}
	
	
}

/*
考察

自然数(mod C)はC個で循環するので
A > C なら　A/C と A%C で
B乗は


*/
0