Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

$1, 2, \dots, 10^{16}$ деп нөмірленген $10^{16}$ қала бар.

Әртүрлі $i, j$ қалалары үшін $i$ қаласы мен $j$ қаласының арасында екі бағытты жол тек $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$ болған жағдайда ғана болады.

$Q$ сұранысқа жауап беріңіз.

$i$-ші сұраныста бүтін $x_i$ саны беріледі. $x_i$ қаласынан нөл немесе одан да көп жолдар арқылы жетуге болатын барлық қалалардың нөмірлерінің бит бойынша XOR мәнін шығарыңыз.

Кіріс деректері

Бірінші жолда бос орын арқылы осы ретпен $A, B$ бүтін сандары берілген. ($1 \le A, B \le 10^8$)

Екінші жолда бүтін $Q$ саны берілген. ($1 \le Q \le 10^5$)

Келесі $Q$ жолдың әрқайсысында $i$-ші сұранысқа арналған бүтін $x_i$ саны берілген. ($1 \le x_i \le 10^{16}$)

Шығыс деректері

$Q$ жол шығарыңыз.

$i$-ші жолда ($1 \le i \le Q$) $i$-ші сұраныстың жауабын шығарыңыз.

Мысалдар

1-мысал кірісі

3 28
4
20
26
7
28

1-мысал шығысы

28
26
54
108

2-мысал кірісі

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

2-мысал шығысы

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Ескертпе

Бірінші мысал үшін $i, j$ қалаларының арасында жолдың болуы $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$ шартына пара-пар.

  • Бірінші сұраныс үшін $20$ қаласынан жетуге болатын қалалар: $8, 20$.
  • Екінші сұраныс үшін $26$ қаласынан жетуге болатын жалғыз қала: $26$.
  • Үшінші сұраныс үшін $7$ қаласынан жетуге болатын қалалар: $7, 49$.
  • Төртінші сұраныс үшін $28$ қаласынан жетуге болатын қалалар: $28, 112$.

Теріс емес бүтін $x, y$ сандарының бит бойынша XOR операциясы $x \oplus y$ келесідей анықталады.

  • $x \oplus y$ санының екілік жазылуында $2^k$ ($k \ge 0$) разрядындағы цифр тек $x$ және $y$ сандарының екілік жазылуларындағы $2^k$ разрядындағы цифрлардың дәл біреуі $1$-ге тең болғанда ғана $1$-ге тең болады; әйтпесе ол $0$-ге тең.

Мысалы, $3 \oplus 5 = 6$ (екілік жүйеде $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.