Project-Euler-1/711.nim at main · MariaChrysafis/Project-Euler-1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
iterator `..`*[T](a: T, b: T): T =
  var res: T = a
  while res <= b:
    yield res
    inc res

const modulo = 1000000007
proc mult (a:clong, b:clong):int =
    return (a * b) mod modulo
proc plus (a:clong, b:clong):int =
    return (a + b) mod modulo
proc binPow(x:clong, y:int):int =
    var res = x
    var ans = 1
    var exp = y
    while exp > 0 :
        if exp mod 2 == 1 :
            ans = mult(ans, res)
        res = mult(res, res)
        exp = exp div 2
    return ans
proc inv (a: clong):int =
    return binPow(a, modulo - 2)
proc divide (a:clong, b:clong):int =
    return (mult(a, inv(b)))
proc minus (a:clong, b:clong):int =
    return (a mod modulo - b mod modulo + modulo) mod modulo
const mx = 12345678

var res = 1
for i in 2..mx :
    if i mod 2 == 0 :
        res = minus(plus(res, binPow(2, i)), 1)
    else :
        res = plus(minus(plus(mult(res, 2), binPow(2, i - 1 + ((i - 1) div 2))), mult(divide((binPow(2, i - 1) - 1), 3), 2)), i div 2)
echo plus(res, binPow(2, mx))