問題一覧 > 教育的問題

No.2972 確率的素数判定

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が10510^{-5} 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 50
作問者 : 👑 p-adic / テスター : Moss_Local
0 ProblemId : 10033 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-10 14:26:07

問題文

確率的素数判定大好きbotは確率的素数判定が大好きなbotです。

確率的素数判定大好きbot大好きbot確率的素数判定大好きbotが大好きなbotです。もちろん 22 体は別物です。

 

ここで次のような問題を考えます:

入力に正整数 NN と、100100 以下の非負整数 P,QP, Q が与えられます。

確率的素数判定大好きbotに正整数を読み込ませると、以下の挙動を示します:

  1. 読み込んだ正整数が素数であるならば、PP %の確率でYesと返答し、(100P)(100 - P) %の確率でNoと返答する。
  2. 読み込んだ正整数が素数でないならば、QQ %の確率でNoと返答し、(100Q)(100 - Q) %の確率でYesと返答する。

確率的素数判定大好きbot大好きbotNN 以下の正整数全体の中から正整数 nn をランダムに(どの正整数が選ばれるかが等確率になるように)選び、確率的素数判定大好きbotに読み込ませました。あなたは nn の値を知りませんが、確率的素数判定大好きbotYesと返答をしたことだけを確認しました。

上記の情報が与えられている状況のもとで nn が素数である確率を求めてください。(以下この値を、この問題に対する答えと呼ぶ)

入力の最初に正整数 TT が与えられます。その後 TT 個の問題に答えてください。

入力

この時、入力は以下の形式で標準入力から 1+T1 + T 行で与えられます:

  • 11 行目に TT が半角空白区切りで与えられます。
  • TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力が 1+t1 + t 行目に与えられます。
TT
(11 個目の問題に対する入力)
\vdots
(TT 個目の問題に対する入力)

TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力は以下の形式で与えられます:

  • N,P,QN, P, Q が半角空白区切りで 11 行で(入力全体の 1+t1 + t 行目に)与えられます。
NN PP QQ

各問題における未知数 nn は入力では与えられません。

制約

入力は以下の制約を満たします:

  • TT1T1051 \leq T \leq 10^5 を満たす整数である。
  • TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力を N,P,QN, P, Q と置くと、
    • NN1N1051 \leq N \leq 10^5 を満たす整数である。
    • PP0<P1000 < P \leq 100 を満たす整数である。
    • QQ0Q1000 \leq Q \leq 100 を満たす整数である。
    • N>1N > 1 かつ 0<P0 < P であるか、または Q<100Q < 100 である。

出力

TT 以下の各正整数 tt に対し、tt 個目の問題に対する答えを小数表示で tt 行目に出力してください。

最後に改行してください。

 

なお、この問題は小数誤差許容問題です。厳密な答えの小数点以下 1010 桁精度近似値からの絶対誤差か相対誤差のいずれかが 10510^{-5} 以下であれば正解となります:

ただしここで実数 xx の小数点以下 1010 桁精度近似値とは、小数点以下高々 1010 桁の有限小数表示を持ち xx を超えない最大の実数を表します。

また、ジャッジ側の都合で各出力は 500500 桁未満にしてください。

サンプル

サンプル1
入力
1
1 90 80
出力
0

確率的素数判定大好きbotYesと返答した事実に関係なく、N=1N = 1 以下の正整数 nn が素数である確率は 00 です。誤差許容問題の仕様上、この他にも

0.00

-0.00001

などと出力しても正解となります。今回は T=1T = 1 であるため、これにて全ての問題に答えられました。

サンプル2
入力
1
2 100 0
出力
0.5

P=100P = 100 かつ Q=0Q = 0 であるため、確率的素数判定大好きbotはどんな正整数を読み込んでもYesと返します。従って確率的素数判定大好きbotYesと返答したという情報は nn が素数であるか否かに関して何の情報も与えません。以上より求める値は nnN=2N = 2 以下の正整数全体 {1,2}\{1,2\} の中からランダムに選ばれた時に nn が素数 22 である確率に他ならず、それは 0.50.5 となります。

今回は T=1T = 1 であるため、これにて全ての問題に答えられました。

サンプル3
入力
2
3 100 100
4 50 50
出力
1
0.5

まず 11 つ目の問題に答えます。今回は P=100P = 100 かつ Q=100Q = 100 であるため、確率的素数判定大好きbotは読み込まれた正整数が素数であるか否かを常に正確に判定します。確率的素数判定大好きbotの返答はYesであったので、nn が素数である確率は 11 です。

次に 22 つ目の問題に答えます。今回は P=50P = 50 かつ Q=50Q = 50 であるため、確率的素数判定大好きbotの返答がYesとなるかNoとなるは nn に依存せずランダムに決まります。従って確率的素数判定大好きbotYesと返答したという情報は nn が素数であるか否かに関して何の情報も与えません。以上より求める値は nnN=4N = 4 以下の正整数全体 {1,2,3,4}\{1,2,3,4\} の中からランダムに選ばれた時に nn が素数 2,32,3 のいずれかである確率に他ならず、それは 0.50.5 となります。

今回は T=2T = 2 であるため、これにて全ての問題に答えられました。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。