問題

xを満たすyがFLAGらしい。

解き方

問題を見たときはモジュロ演算なんて言葉は知らなかったけど、取りあえず累乗根を単純に計算するだけだと思った。

ささっと計算してみたらオーバーフローしてうまく動かない。
多分これは私の書き方とかそもそも論で何か間違っているのだろう。

    y = pow (x,(1.00/101.00))
OverflowError: long int too large to convert to float

どうすればいいのか調べていたら二分探索で解を得るのがベターらしい。

二分探索をやってみる

二分探索はここを参考にした。

二分探索と聞いたときは「基本情報でなんか見たかも」ぐらいな感じで、使ったことは一回もなかった。

# python3
import math

x = ここに問題文の値を入れる

y_min = 0
y_max = 10 ** 300 #ここは適当
y_jou = 101

for num in range(0,2000): # 2000も適当
  mid = ( y_min + y_max ) // 2
  dy = pow (mid , y_jou)
  if dy == x:
    print (mid)
    break
  elif dy > x:
    y_max = mid
    print ("大きすぎ")
  elif dy < x:
    y_min = mid
    print ("小さすぎ")
  keta = int(math.log10(mid)+1)
  print (str(num) + ": " + str(keta) + "桁")

なんとなくやっていることを理解して、雰囲気で実装してみたけど一応答えはでた。

その他

問題に書かれていたモジュロ演算はRSA暗号で使われているらしい。
※RSA暗号は公開鍵暗号の一つ

参考

http://www.mew.org/~kazu/doc/rsa.html

http://www.maitou.gr.jp/rsa/rsa09.php

http://herb.h.kobe-u.ac.jp/RSA.html

[asin:B01MDKUQ6M:detail]