丸め誤差や浮動小数点数をあまり理解していないが故のWAです。備忘として残しておきます。
コンテンツ一覧
D問題でWA
提出したプログラムはこれです。（WA）
import math
T = int(input())
def find_prime(n):
for i in range(2,int(n**0.5)+1):
if n%i == 0:
return i
for _ in range(T):
t = int(input())
p1 = find_prime(t)
if t%(p1**2) == 0:
print(p1,int(t/p1**2))
else:
print(int(math.sqrt(t/p1)),p1)入力される正整数 \(\ N \) は２つの相異なる素数\(\ p,q \) を用いて \(\ N = p^2 q \) で表せることが分かっているので、取り敢えず構成している素数のうちどっちか一つ分かれば良いです。
\(\ find prime \) 関数で割り試しを行い、素数を一つ見つけてきます。それが \(\ p,q \) のうちどちらかは実際に二乗して剰余演算を行って判定します。
WAとなり、なんとなく誤差のせいだとは分かりましたが、math.sqrtをずっと疑ってしましました。
結論、「int(t/p1**2)」という書き方が悪く、「it//p1**2」と切り捨て除算を行えばACとなります。
整数除算では切り捨て除算（//）を使う
コンピュータ演算では、大きな数を小さな数で除算する時などに誤差が発生することがあります。これは精度誤差などと言って、コンピュータ上で表現できる桁数に限りがある為に発生する誤差です。無限桁の小数などは必ずあるため精度誤差は必ず生じるものですが、これを小さくする工夫は必要です。
例えば以下のように、大きな桁数の数字を小さな数で割る場合、除算結果が有効桁数を超えるため、桁が小さい部分が近似されて誤差が発生します。
import math
a = 10**19
b = 333
print(a/b) #3.003003003003003e+16
print(int(a/b)) #30030030030030032
print(math.floor(a/b)) #30030030030030032
print(a//b) #切り捨て除算 30030030030030030整数同士の除算の場合は、切り捨て除算（//）を用いることで誤差を抑えることができます。通常の除算（/）では小数点以下の数値を保持したまま計算しますが、切り捨て除算（//）では小数点以下を切り捨てて計算します。小数点以下を切り捨てて計算した場合、精度の低下の影響は小数点以下だけに限られます。求める数値が整数の場合、小数点以下の精度は必要ないので、切り捨てて計算したほうが求めている数値になりやすいということです。
また、処理速度という面でもこの場合、切り捨て除算を用いた方が高速です。通常除算で小数点以下を保持して計算した後、intやfloorで小数点以下を切り捨てるよりも、切り捨て除算で内部的に最初から小数点以下を切り捨てて計算したほうが計算量も少なくすみます。
これの競技プログラミング的な罠（？）なところは、上記プログラムの \(\ b \) が \(\ a \) に比べてそれほど小さくなければ、切り捨てだろうが通常除算だろうが結果が同じになることです。
import math
a = 10**19
b = 33300000
print(a/b) #300300300300.3003
print(a//b) #300300300300
print(int(a/b)) #300300300300
print(math.floor(a/b)) #300300300300入力例のテストケースでは問題ないのに、提出したら数問だけWAになる場合、こういった誤差へのケアが足りていないことも考えられます。
なんとなく誤差のせいなんだろうと分かっていても、内部的に誤差が発生する仕組みを理解していないと、どこで誤差が発生しているのか分からないことがあるので、こういった知識もちゃんと頭に入れておくべきだと感じました。。