[BOJ 9756] Goldbach (Extension of Goldbach’s Conjecture)
View as PDFกำ หนดให้m เป็นจำ นวนเตม็ บวกจำ นวนหน่ึง เพรำะเรำทรำบวำ่ ปัญหำกำรหำจำ นวนเฉพำะสองจำ นวนมำบวกกนั ใหไ้ด้m เมื่อ m เป็ น จำ นวนเตม็คู่ที่มำกกวำ่ หรือเท่ำกบั สี่ หรือปัญหำกำรหำจำ นวนเฉพำะสำมจำ นวนมำบวกกนั ใหไ้ด้m เมื่อ m เป็นจำ นวนเตม็คี่ที่มำกกวำ่ เจ็ด เป็นปัญหำที่ยงัไม่มีอลักอริทึมใดๆ มำหำคำ ตอบได้หรือแมแ้ต่จะพิสูจน์วำ่ หำคำ ตอบไดเ้สมอยงัไม่มีใครทำ ไดใ้นขณะน้ีดงัน้นั เพื่อ ทำ ใหค้วำมซบั ซอ้ นของกำรหำคำ ตอบง่ำยข้ึน เรำพบวำ่ จริงๆ แลว้ หำกตอ้งกำรหำจำ นวนที่นำ มำบวกกนัแลว้มีค่ำเท่ำกบั m 3 มีโอกำส มำกกวำ่ m ในกำรมีคำ ตอบได้แต่เพื่อไม่ใหก้ำรหำคำ ตอบง่ำยเกินไปและกำรตรวจคำ ตอบยำกเกินไป (เพรำะอำจมีคำ ตอบไดม้ำกกวำ่ หน่ึงกรณี) ดงัน้นัแทนที่จะหำจำ นวนเฉพำะมำบวก เรำจะหำจำ นวนเตม็คี่ที่เรียงถดักนั m จ ำนวนมำแทน ซึ่งหำกเขียนได้ จะมีเพียงชุด เดียวเท่ำน้นั เช่น กำ หนดให้m = 2 เรำจะไดว้ำ่ m 3 สำมำรถเขียนใหอ้ยใู่ นรูปของผลบวกของจำ นวนเตม็คี่ได้สองจำ นวนที่เรียงถดักนัคือ 3 + 5 (เพรำะ 23 = 8)
입력 형식
แต่ละบรรทดัจะมีเลขจำ นวนเตม็ บวก m โดยที่ m ≤ 1,000,000,000 บรรทัดสุดท้ำย m จะมีค่ำเท่ำกบัศูนย์ซ่ึงหมำยถึงจบขอ้มูลนำ เขำ้ โดยจำ นวนขอ้มูลนำ เขำ้ มีจำ นวนไม่เกิน 100 จ ำนวน
출력 형식
แต่ละบรรทดัจะแสดงผลของขอ้มูลแต่ละค่ำของ m โดย ประกอบดว้ย สองส่วนคือ A และ B คนั่ ดว้ยspace หน่ึงคร้ัง ท้งัน้ี</p>
A มีค่ำเป็น Y ในกรณีที่สำมำรถหำจ ำนวนเต็มคี่ m จำ นวนที่เรียงถดักนัและบวกกนั เท่ำกบั m3 ได้ N ในกรณีที่ไม่สำมำรถหำคำ ตอบได้
B เป็นคำของจ ำนวนเต็มคี่ตัวแรกจำก ่ m ตวัที่นำ มำบวกกนัแลว้มีค่ำเท่ำกบั m3 เฉพำะในกรณีที่ A = Y ไม่เช่นน้นั ใหแ้ สดงค่ำ B = 0
예제 입력
2
3
0
예제 출력
Y 3
Y 7
Comments