Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Terdapat $10^{16}$ kota yang diberi label $1, 2, \dots, 10^{16}$.

Untuk kota-kota berbeda $i, j$, terdapat jalan dua arah antara kota $i$ dan kota $j$ jika dan hanya jika $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.

Jawablah $Q$ kueri.

Pada kueri ke-$i$, diberikan sebuah bilangan bulat $x_i$. Keluarkan hasil XOR bitwise dari label semua kota yang dapat dicapai dari kota $x_i$ dengan melewati nol atau lebih jalan.

Masukan

Baris pertama berisi bilangan bulat $A, B$ dalam urutan tersebut, dipisahkan oleh spasi. ($1 \le A, B \le 10^8$)

Baris kedua berisi sebuah bilangan bulat $Q$. ($1 \le Q \le 10^5$)

Masing-masing dari $Q$ baris berikutnya berisi sebuah bilangan bulat $x_i$ untuk kueri ke-$i$. ($1 \le x_i \le 10^{16}$)

Keluaran

Cetak $Q$ baris.

Pada baris ke-$i$ ($1 \le i \le Q$), keluarkan jawaban untuk kueri ke-$i$.

Contoh

Contoh Masukan 1

3 28
4
20
26
7
28

Contoh Keluaran 1

28
26
54
108

Contoh Masukan 2

81781525 3945925
10
53907475
6160906250298067
3007621769603801
134161450
23675550
4034161385146811
2151358558435
12908151350610
112647860153451
9491287293575

Contoh Keluaran 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Catatan

Untuk contoh pertama, keberadaan jalan antara kota $i, j$ setara dengan $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.

  • Untuk kueri pertama, kota-kota yang dapat dicapai dari kota $20$ adalah $8, 20$.
  • Untuk kueri kedua, satu-satunya kota yang dapat dicapai dari kota $26$ adalah $26$.
  • Untuk kueri ketiga, kota-kota yang dapat dicapai dari kota $7$ adalah $7, 49$.
  • Untuk kueri keempat, kota-kota yang dapat dicapai dari kota $28$ adalah $28, 112$.

XOR bitwise $x \oplus y$ dari bilangan bulattak negatif $x, y$ didefinisikan sebagai berikut.

  • Dalam representasi biner dari $x \oplus y$, digit pada nilai tempat $2^k$ ($k \ge 0$) bernilai $1$ jika dan hanya jika tepat satu dari digit pada nilai tempat $2^k$ dalam representasi biner dari $x$ dan $y$ bernilai $1$; selain itu, nilainya adalah $0$.

Sebagai contoh, $3 \oplus 5 = 6$ (dalam biner, $011 \oplus 101 = 110$).

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1527EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.