![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="48" height="48"><rect fill-opacity="0"/></svg>)
AさんとBさんとCさんがゲームをします
最初に、 C さんはある正整数 X, Y をAさんに渡します
A さんは X に好きな整数を掛けて B さんに渡します
このとき、 B さんが Y を知る方法を考えてください
なお、 A さんと B さんは事前に話し合って方法を共有することができます
9
5
21
Tweet
Conversation
Replying to
割とネタ寄りな方法ですが
A さんは X より大きい最小の素数 p を計算し X*p^Y を渡す。B さんは受け取った整数を素因数分解に最も大きい素因数の指数を答える。
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24"><rect fill-opacity="0"/></svg>)
いや、これ桁数とか計算量とか膨れ上がるしないなーと思いつつだったので…
New to Twitter?
Sign up now to get your own personalized timeline!
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="240" height="135"><rect fill-opacity="0"/></svg>)
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="120" height="80"><rect fill-opacity="0"/></svg>)
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="120" height="90"><rect fill-opacity="0"/></svg>)