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

Det finnes $10^{16}$ byer, nummerert $1, 2, \dots, 10^{16}$.

For ulike byer $i, j$ går det en toveis vei mellom by $i$ og by $j$ hvis og bare hvis $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.

Svar på $Q$ spørringer.

I den $i$-te spørringen gis et heltall $x_i$. Skriv ut den bitvise XOR-verdien av numrene til alle byer som kan nås fra by $x_i$ ved å følge null eller flere veier.

Inndata

Den første linjen inneholder heltallene $A, B$ i denne rekkefølgen, adskilt med mellomrom. ($1 \le A, B \le 10^8$)

Den andre linjen inneholder et heltall $Q$. ($1 \le Q \le 10^5$)

Hver av de påfølgende $Q$ linjene inneholder et heltall $x_i$ for den $i$-te spørringen. ($1 \le x_i \le 10^{16}$)

Utdata

Skriv ut $Q$ linjer.

På den $i$-te linjen ($1 \le i \le Q$) skal du skrive ut svaret på den $i$-te spørringen.

Eksempler

Eksempelinndata 1

3 28
4
20
26
7
28

Eksempelutdata 1

28
26
54
108

Eksempelinndata 2

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

Eksempelutdata 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Forklaring

For det første eksempelet tilsvarer eksistensen av en vei mellom byene $i, j$ at $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.

  • For den første spørringen er byene som kan nås fra by $20$ lik $8, 20$.
  • For den andre spørringen er den eneste byen som kan nås fra by $26$ lik $26$.
  • For den tredje spørringen er byene som kan nås fra by $7$ lik $7, 49$.
  • For den fjerde spørringen er byene som kan nås fra by $28$ lik $28, 112$.

Den bitvise XOR-verdien $x \oplus y$ for ikke-negative heltall $x, y$ er definert som følger.

  • I den binære representasjonen av $x \oplus y$ er sifferet på $2^k$-plassen ($k \ge 0$) lik $1$ hvis og bare hvis nøyaktig ett av sifrene på $2^k$-plassen i de binære representasjonene av $x$ og $y$ er $1$; ellers er det $0$.

For eksempel er $3 \oplus 5 = 6$ (i binær form, $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.