AさんとBさんとCさんがゲームをします
最初に、 C さんはある正整数 X, Y をAさんに渡します
A さんは X に好きな整数を掛けて B さんに渡します
このとき、 B さんが Y を知る方法を考えてください
なお、 A さんと B さんは事前に話し合って方法を共有することができます
Tweet
Conversation
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="48" height="48"><rect fill-opacity="0"/></svg>)
プライバシーの保護のため答えることはできません
1
Show replies
Replying to
A さんは X を素因数分解し、その最も大きな素因数 (ただし X=1 のときは 1 とする) の Y 個次の素数を X に掛けて B さんに渡す。B さんは受け取った整数を素因数分解し、その大きいほうから 2 つの素因数の間の素数の個数を数えて答える。
1
2
ACです！
想定解はちょっと違いますが、似ています
1
Replying to
A さんはいかなる平方数でも割り切れない Y 番目に小さい正の整数を求め、それを Z としたとき X^2*Z を渡す。B さんは受け取った整数をできるだけ大きい平方数で割り切り、残った数がいかなる平方数でも割り切れない正の整数のうち何番目に小さいか数えて答える。
1
1
2
1 以外の平方数で割り切れない、でした
2
例えば (x, y) = (10, 1) のとき死にませんか？（x の整数倍はどうやっても k>=1 かつ (桁数)>=2 なので）
1
1
Show replies
Replying to
割とネタ寄りな方法ですが
A さんは X より大きい最小の素数 p を計算し X*p^Y を渡す。B さんは受け取った整数を素因数分解に最も大きい素因数の指数を答える。
1
2
え、これ想定解でしたか (すみません)
Quote Tweet
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="24" height="24"><rect fill-opacity="0"/></svg>)
まぐふらい
@magrofly
·
想定解は最大の素因数よりひとつ大きい素数をpとして、p^Yをかける、でした（最悪）
1
1
Show replies
Replying to
こんなのはどうでしょうか？ X, Yを素因数分解して、ある素因数pの次数をa, bとしたとき、2^k>max(a, b)となる整数kをとってきて2^k+bがpの次数になるような整数を渡す→素因数分解して次数のmsbを落とせばYが復元できる
1
![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="680" height="357"><rect fill-opacity="0"/></svg>)
Show more replies
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="90"><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>)