Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Es gibt $10^{16}$ Städte, die mit $1, 2, \dots, 10^{16}$ nummeriert sind.

Für verschiedene Städte $i, j$ gibt es genau dann eine Straße in beide Richtungen zwischen Stadt $i$ und Stadt $j$, wenn $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$ gilt.

Beantworte $Q$ Anfragen.

In der $i$-ten Anfrage ist eine ganze Zahl $x_i$ gegeben. Gib das bitweise XOR der Nummern aller Städte aus, die von Stadt $x_i$ aus über null oder mehr Straßen erreichbar sind.

Eingabe

Die erste Zeile enthält die ganzen Zahlen $A, B$ in dieser Reihenfolge, getrennt durch Leerzeichen. ($1 \le A, B \le 10^8$)

Die zweite Zeile enthält eine ganze Zahl $Q$. ($1 \le Q \le 10^5$)

Jede der folgenden $Q$ Zeilen enthält eine ganze Zahl $x_i$ für die $i$-te Anfrage. ($1 \le x_i \le 10^{16}$)

Ausgabe

Gib $Q$ Zeilen aus.

Gib in der $i$-ten Zeile ($1 \le i \le Q$) die Antwort auf die $i$-te Anfrage aus.

Beispiele

Beispieleingabe 1

3 28
4
20
26
7
28

Beispielausgabe 1

28
26
54
108

Beispieleingabe 2

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

Beispielausgabe 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Hinweis

Für das erste Beispiel ist die Existenz einer Straße zwischen den Städten $i, j$ äquivalent zu $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.

  • Für die erste Anfrage sind die von Stadt $20$ aus erreichbaren Städte $8, 20$.
  • Für die zweite Anfrage ist die einzige von Stadt $26$ aus erreichbare Stadt $26$.
  • Für die dritte Anfrage sind die von Stadt $7$ aus erreichbaren Städte $7, 49$.
  • Für die vierte Anfrage sind die von Stadt $28$ aus erreichbaren Städte $28, 112$.

Das bitweise XOR $x \oplus y$ nichtnegativer ganzer Zahlen $x, y$ ist wie folgt definiert.

  • In der Binärdarstellung von $x \oplus y$ ist die Ziffer an der Stelle $2^k$ ($k \ge 0$) genau dann $1$, wenn genau eine der Ziffern an der Stelle $2^k$ in den Binärdarstellungen von $x$ und $y$ gleich $1$ ist; andernfalls ist sie $0$.

Beispielsweise gilt $3 \oplus 5 = 6$ (binär $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.