123456789101112131415161718192021222324252627282930313233343536373839404142434445 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 28 April 2023
- # https://github.com/trizen
- # https://projecteuler.net/problem=435
- # Runtime: 5.001s
- var congruences = []
- 15!.factor_map { |p,e|
- var n = 10**15
- var pp = p**e
- var sum = 0
- var (f1, f2) = (0, 1)
- var arr = []
- for k in (1..n) {
- var power_sum = 0
- for x in (1..100) {
- power_sum.addmod!(powmod(x, k, pp), pp)
- }
- sum.addmulmod!(f2, power_sum, pp)
- arr << sum
- (f1, f2) = (f2, addmod(f1, f2, pp))
- if ((f1 == 0) && (f2 == 1) && (arr.slice(9, (arr.len>>1)-9) == arr.slice(arr.end>>1 + 10))) {
- sum = arr[(n % k)-1]
- break
- }
- }
- congruences << [sum, pp]
- }
- say Math.chinese(congruences...)
|