Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Det finns $10^{16}$ städer, numrerade $1, 2, \dots, 10^{16}$.

För skilda städer $i, j$ finns det en dubbelriktad väg mellan stad $i$ och stad $j$ om och endast om $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.

Besvara $Q$ frågor.

I den $i$-te frågan ges ett heltal $x_i$. Skriv ut det bitvisa XOR-värdet av numren på alla städer som kan nås från stad $x_i$ genom att färdas längs noll eller flera vägar.

Indata

Den första raden innehåller heltalen $A, B$ i denna ordning, åtskilda av blanksteg. ($1 \le A, B \le 10^8$)

Den andra raden innehåller ett heltal $Q$. ($1 \le Q \le 10^5$)

Var och en av de följande $Q$ raderna innehåller ett heltal $x_i$ för den $i$-te frågan. ($1 \le x_i \le 10^{16}$)

Utdata

Skriv ut $Q$ rader.

På den $i$-te raden ($1 \le i \le Q$) ska du skriva ut svaret på den $i$-te frågan.

Exempel

Exempelindata 1

3 28
4
20
26
7
28

Exempelutdata 1

28
26
54
108

Exempelindata 2

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

Exempelutdata 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Förklaring

För det första exemplet är existensen av en väg mellan städerna $i, j$ ekvivalent med $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.

  • För den första frågan är städerna som kan nås från stad $20$ lika med $8, 20$.
  • För den andra frågan är den enda staden som kan nås från stad $26$ lika med $26$.
  • För den tredje frågan är städerna som kan nås från stad $7$ lika med $7, 49$.
  • För den fjärde frågan är städerna som kan nås från stad $28$ lika med $28, 112$.

Det bitvisa XOR-värdet $x \oplus y$ för icke-negativa heltal $x, y$ definieras enligt följande.

  • I den binära representationen av $x \oplus y$ är siffran på platsen $2^k$ ($k \ge 0$) lika med $1$ om och endast om exakt en av siffrorna på platsen $2^k$ i de binära representationerna av $x$ och $y$ är $1$; annars är den $0$.

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