Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Það eru $10^{16}$ borgir, númeraðar $1, 2, \dots, 10^{16}$.

Fyrir ólíkar borgir $i, j$ liggur tvístefnuvegur á milli borgar $i$ og borgar $j$ ef og aðeins ef $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.

Svaraðu $Q$ fyrirspurnum.

Í $i$-tu fyrirspurninni er gefin heiltala $x_i$. Skrifaðu út bitavísað XOR af númerum allra borga sem hægt er að komast til frá borg $x_i$ með því að fara um núll eða fleiri vegi.

Inntak

Fyrsta línan inniheldur heiltölurnar $A, B$ í þessari röð, aðskildar með bilum. ($1 \le A, B \le 10^8$)

Önnur línan inniheldur heiltölu $Q$. ($1 \le Q \le 10^5$)

Hver af næstu $Q$ línum inniheldur heiltölu $x_i$ fyrir $i$-tu fyrirspurnina. ($1 \le x_i \le 10^{16}$)

Úttak

Prentaðu $Q$ línur.

Á $i$-tu línu ($1 \le i \le Q$) skal skrifa út svarið við $i$-tu fyrirspurninni.

Dæmi

Dæmi um inntak 1

3 28
4
20
26
7
28

Dæmi um úttak 1

28
26
54
108

Dæmi um inntak 2

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

Dæmi um úttak 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Athugasemd

Í fyrra dæminu jafngildir tilvist vegar á milli borga $i, j$ skilyrðinu $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.

  • Í fyrstu fyrirspurninni eru borgirnar sem komast má til frá borg $20$ borgirnar $8, 20$.
  • Í annarri fyrirspurninni er eina borgin sem komast má til frá borg $26$ borgin $26$.
  • Í þriðju fyrirspurninni eru borgirnar sem komast má til frá borg $7$ borgirnar $7, 49$.
  • Í fjórðu fyrirspurninni eru borgirnar sem komast má til frá borg $28$ borgirnar $28, 112$.

Bitavísað XOR $x \oplus y$ afóneikvæðum heiltölum $x, y$ er skilgreint sem hér segir.

  • Í tvíundarframsetningu $x \oplus y$ er tölustafurinn í sæti $2^k$ ($k \ge 0$) jafn $1$ ef og aðeins ef nákvæmlega annar tölustafanna í sæti $2^k$ í tvíundarframsetningum $x$ og $y$ er $1$; annars er hann $0$.

Til dæmis er $3 \oplus 5 = 6$ (í tvíundarkerfi, $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.