Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

有 $10^{16}$ 座城市,編號為 $1, 2, \dots, 10^{16}$。

對於唔同嘅城市 $i, j$,當且僅當 $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$ 嗰陣,城市 $i$ 同城市 $j$ 之間存在一條雙向道路。

請回答 $Q$ 個查詢。

喺第 $i$ 個查詢入面,會俾出一個整數 $x_i$。請輸出由城市 $x_i$ 出發,經過零條或者多條道路可以到達嘅所有城市編號嘅按位異或(bitwise XOR)和。

輸入格式

第一行按順序包含整數 $A, B$,中間用空格隔開。($1 \le A, B \le 10^8$)

第二行包含一個整數 $Q$。($1 \le Q \le 10^5$)

接下來嘅 $Q$ 行,每行包含一個整數 $x_i$,代表第 $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$ 嘅按位異或 $x \oplus y$ 定義如下:

  • 喺 $x \oplus y$ 嘅二進制表示入面,$2^k$($k \ge 0$)位上面嘅數字係 $1$,當且僅當 $x$ 同 $y$ 嘅二進制表示喺 $2^k$ 位上面嘅數字恰好有一個係 $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.