Matej Focko
96f59f9f54
URL: https://leetcode.com/problems/count-good-numbers/ Signed-off-by: Matej Focko <me@mfocko.xyz>
22 lines
320 B
Go
22 lines
320 B
Go
package main
|
|
|
|
const (
|
|
MOD int64 = 1000000007
|
|
)
|
|
|
|
func countGoodNumbers(n int64) int {
|
|
quickmul := func(x, y int64) int64 {
|
|
res := int64(1)
|
|
for y > 0 {
|
|
if y%2 == 1 {
|
|
res = (res * x) % MOD
|
|
}
|
|
x = (x * x) % MOD
|
|
y /= 2
|
|
}
|
|
|
|
return res
|
|
}
|
|
|
|
return int((quickmul(5, (n+1)/2) * quickmul(4, n/2)) % MOD)
|
|
}
|