cal_mod.go

// same https://play.golang.org/p/3vGkbJ8OiNC

package main

const C = 12345678

func power(x, y int64) int64 {
	a := int64(1)
	for ; ; {
		if (y & 1) != 0 {
			a = x * a
		}
		y = y >> 1
		if y == 0 {
			return a
		}
		x *= x
	}

	return a
}

func calm(a, n int64) int64 {
	if a > C {
		a %= C
	}

	if n == 0 {
		return 1
	}

	if n == 1 || a == 0 || a == 1 {
		return a
	}

	loopTime := int64(1)

	b := a
	for ; ; {
		if b > C {
			break
		}
		b *= a
		loopTime += 1
	}
	loopPower := n / loopTime
	if loopPower == 0 {
		return power(a, n-loopTime*loopPower)
	}
	return power(a, n-loopTime*loopPower) * calm(power(a, loopTime), loopPower)
}

func calc(n int64) int64 {
	s := int64(0)
	for i := int64(1); i <= n; i++ {
		s = (s + calm(i, i)) % C
	}
	return s
}

func main() {
	println(calc(5000000))
}