fork download
copy 
  1. # a, b が与えられたとき ax + by = gcd(a, b) となる x, y を返す
  2. def euclid(a, b)
  3.   return [0, 1] if a == 0
  4.   x, y = euclid(b % a, a)
  5.   [y - b / a * x, x]
  6. end
  7.  
  8. N = 123456789
  9. M = 10 ** 9
  10.  
  11. max = 0
  12. (M - 1).step(1, -2) do |x|
  13. 	next if x % 5 == 0
  14. 	break if x * (M - 1) <= max
  15. 	y = euclid(x, M).first * N % M * x
  16. 	max = y if y > max
  17. end
  18.  
  19. p max
Success #stdin #stdout 0.08s 7456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
999977770123456789
https://ideone.com/szUzdk
language:
Ruby (ruby 2.5.5)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!