diff options
Diffstat (limited to 'euler_684.py')
-rw-r--r-- | euler_684.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/euler_684.py b/euler_684.py new file mode 100644 index 0000000..f5bbec7 --- /dev/null +++ b/euler_684.py @@ -0,0 +1,36 @@ +#!/usr/bin/env python + +_mod = 1000000007 + +def expmod(a,n,m): + if n == 0: + return 1 + + if n % 2 == 0: + t = expmod(a,n>>1,m) + return (t*t)%m + else: + return (a*expmod(a,n-1,m))%m + +def S(k): + n = k // 9 + m = k % 9 + pwr = expmod(10,n,_mod) + return 5*(pwr-1)-9*n+pwr*(m+2)*(m+1)//2-(m+1) + +def main(): + fib = [0]*91 + fib[0] = 0 + fib[1] = 1 + for i in range(2,91): + fib[i] = fib[i-2]+fib[i-1] + + ans = 0 + for i in range(2,91): + print(i) + ans = (ans + S(fib[i])) % _mod + + print(ans) + +if __name__ == "__main__": + main() |