คำอธิบายโจทย์
กำหนดจำนวนเต็มบวก $N$
จงหาจำนวนคู่ของจำนวนเต็ม $(a, b)$ ที่ $1 \le a, b < 2^N$ และสอดคล้องกับเงื่อนไขต่อไปนี้ มอดูโลจำนวนเฉพาะ $998244353$:
- มีรูปสามเหลี่ยมไม่ลดรูปที่มีความยาวด้านเป็น $a, b, a \oplus b$
ในที่นี้ สำหรับจำนวนเต็ม $x, y$ สัญลักษณ์ $x \oplus y$ แทนการดำเนินการ XOR ระดับบิตของ $x$ และ $y$
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $N$ ($1 \le N \le 10^{18}$)
ข้อมูลส่งออก
พิมพ์จำนวนคู่ของจำนวนเต็ม $(a, b)$ ที่สอดคล้องกับเงื่อนไข มอดูโลจำนวนเฉพาะ $998244353$
ตัวอย่าง
ข้อมูลนำเข้า 1
2
ข้อมูลส่งออก 1
0
ข้อมูลนำเข้า 2
5
ข้อมูลส่งออก 2
390
คำอธิบาย
สำหรับตัวอย่างที่สอง ยกตัวอย่างเช่น $(a, b) = (13, 24)$ สอดคล้องกับเงื่อนไข เนื่องจาก $a \oplus b = 13 \oplus 24 = 21$ จึงมีรูปสามเหลี่ยมไม่ลดรูปที่มีความยาวด้านเป็น $13, 24, 21$
มีคู่ของจำนวนเต็ม $(a, b)$ ที่สอดคล้องกับเงื่อนไขทั้งหมด $390$ คู่
ข้อมูลนำเข้า 3
10000
ข้อมูลส่งออก 3
851087540
คำใบ้
การดำเนินการ XOR ระดับบิต $x \oplus y$ ของจำนวนเต็มไม่ลบ $x, y$ นิยามดังนี้:
- ในการเขียนแทนด้วยเลขฐานสองของ $x \oplus y$ เลขโดดในหลัก $2^k$ ($k \ge 0$) จะเป็น $1$ ก็ต่อเมื่อในการเขียนแทนด้วยเลขฐานสองของ $x$ และ $y$ มีเลขโดดในหลัก $2^k$ เพียงตัวเดียวเท่านั้นที่เป็น $1$ มิฉะนั้นจะเป็น $0$
ตัวอย่างเช่น $3 \oplus 5 = 6$ (ในเลขฐานสองคือ $011 \oplus 101 = 110$)