C - 4/N

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

4/N = 1/h + 1/n + 1/w を満たす正整数 h, n, w を求めよ。

制約

• N に対して h, n, w \leq 3500 となる解が存在することが保証される。

入力

N

出力

h n w

入力例 1

2

出力例 1

1 2 2

4/2 = 1/1 + 1/2 + 1/2である。

入力例 2

3485

出力例 2

872 1012974 1539173474040

入力例 3

4664

出力例 3

3498 3498 3498

Score : 300 points

Problem Statement

You are given an integer N.

Find a triple of positive integers h, n and w such that 4/N = 1/h + 1/n + 1/w.

If there are multiple solutions, any of them will be accepted.

Constraints

• It is guaranteed that, for the given integer N, there exists a solution such that h,n,w \leq 3500.

Inputs

Input is given from Standard Input in the following format:

N


Outputs

Print a triple of positive integers h, n and w that satisfies the condition, in the following format:

h n w


Sample Input 1

2


Sample Output 1

1 2 2


4/2 = 1/1 + 1/2 + 1/2.

Sample Input 2

3485


Sample Output 2

872 1012974 1539173474040


It is allowed to use an integer exceeding 3500 in a solution.

Sample Input 3

4664


Sample Output 3

3498 3498 3498

D - IntegerotS

Time Limit: 2 sec / Memory Limit: 256 MB

制約

• 1 \leq N \leq 10^5
• 0 \leq K < 2^{30}
• 0 \leq A_i < 2^{30}(1\leq i\leq N)
• 1 \leq B_i \leq 10^9(1\leq i\leq N)
• 入力は全て整数である

入力

N K
A_1 B_1
:
A_N B_N


入力例 1

3 5
3 3
4 4
2 5


出力例 1

8


23 を購入することで、最大値 8 を達成できます。

入力例 2

3 6
3 3
4 4
2 5


出力例 2

9


24 を購入することで、最大値 9 を達成できます。

入力例 3

7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9


出力例 3

32


Score : 500 points

Problem Statement

Seisu-ya, a store specializing in non-negative integers, sells N non-negative integers. The i-th integer is A_i and has a utility of B_i. There may be multiple equal integers with different utilities.

Takahashi will buy some integers in this store. He can buy a combination of integers whose bitwise OR is less than or equal to K. He wants the sum of utilities of purchased integers to be as large as possible.

Find the maximum possible sum of utilities of purchased integers.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq K < 2^{30}
• 0 \leq A_i < 2^{30}(1\leq i\leq N)
• 1 \leq B_i \leq 10^9(1\leq i\leq N)
• All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N K
A_1 B_1
:
A_N B_N


Outputs

Print the maximum possible sum of utilities of purchased integers.

Sample Input 1

3 5
3 3
4 4
2 5


Sample Output 1

8


Buy 2 and 3 to achieve the maximum possible total utility, 8.

Sample Input 2

3 6
3 3
4 4
2 5


Sample Output 2

9


Buy 2 and 4 to achieve the maximum possible total utility, 9.

Sample Input 3

7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9


Sample Output 3

32

E - CARtesian Coodinate

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

xy 平面上に直線が N 本あります。i 本目の直線は、A_ix+B_iy=C_i で表される直線です。 これら N 直線と、x 軸、y 軸を合わせた合計 N+2 本の直線のうちどの相異なる 2 本をとっても、ちょうど 1 点で交わります。

制約

• 2 ≦ N ≦ 4 × 10^4
• 1 ≦ |A_i|,|B_i| ≦ 10^4(1 ≦ i ≦ N)
• 0 ≦ |C_i| ≦ 10^4(1 ≦ i ≦ N)
• 与えられるどの 2 直線も平行でない
• 入力は全て整数である

入力

N
A_1 B_1 C_1
:
A_N B_N C_N


入力例 1

3
1 1 1
2 -1 2
-1 2 2


出力例 1

1.000000000000000 1.000000000000000


入力例 2

4
1 1 2
1 -1 0
3 -1 -2
1 -3 4


出力例 2

-1.000000000000000 -1.000000000000000


入力例 3

7
1 7 8
-2 4 9
3 -8 -5
9 2 -14
6 7 5
-8 -9 3
3 8 10


出力例 3

-1.722222222222222 1.325000000000000


Score : 800 points

Problem Statement

There are N lines in the xy-plane. The i-th line is represented by A_ix+B_iy=C_i. Any two lines among the N+2 lines, the above N lines plus the x-axis and y-axis, cross each other at exactly one point.

For each pair 1 \leq i < j \leq N, there is a car at the cross point of the i-th and j-th lines. Even where three or more lines intersect at a point, a car is individually placed for each pair of lines. That is, there will be k(k-1)/2 cars placed at the intersection of k lines.

Those cars are already very old, and can only be moved parallel to the x-axis or y-axis.

Takahashi will hold an exhibition of antique cars at a place on the xy-plane. In order to avoid damaging the half-broken cars too much, he will select the place of the exhibition so that the total distance covered will be minimized when all the cars are moved to the place. If such a place is not uniquely determined, among the places that satisfy the condition above, the place with the minimum x-coordinate will be selected. If the place is still not uniquely determined, among the places that satisfy the two conditions above, the place with the minimum y-coordinate will be selected.

Find the place of the exhibition that will be selected.

Constraints

• 2 \leq N \leq 4 × 10^4
• 1 \leq |A_i|,|B_i| \leq 10^4(1 \leq i \leq N)
• 0 \leq |C_i| \leq 10^4(1 \leq i \leq N)
• No two given lines are parallel.
• All input values are integers.

Inputs

Input is given from Standard Input in the following format:

N
A_1 B_1 C_1
:
A_N B_N C_N


Outputs

Print the x-coordinate and y-coordinate of the place of the exhibition that will be selected, in this order, with a space in between. The output will be judged as correct when the absolute or relative error is at most 10^{-9}.

Sample Input 1

3
1 1 1
2 -1 2
-1 2 2


Sample Output 1

1.000000000000000 1.000000000000000


There is a car at each place shown by a blue circle in the figure. The place to be selected is shown by a purple circle.

Sample Input 2

4
1 1 2
1 -1 0
3 -1 -2
1 -3 4


Sample Output 2

-1.000000000000000 -1.000000000000000


Sample Input 3

7
1 7 8
-2 4 9
3 -8 -5
9 2 -14
6 7 5
-8 -9 3
3 8 10


Sample Output 3

-1.722222222222222 1.325000000000000

F - ModularPowerEquation!!

Time Limit: 2 sec / Memory Limit: 256 MB

制約

• 1 \leq Q \leq 100
• 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
• 1 \leq M_i \leq 10^9(1 \leq i \leq Q)

入力

Q
A_1 M_1
:
A_Q M_Q


出力

i 行目には、i 個目のクエリに対し、問題文の条件を満たす K_i が存在しないなら、-1 を出力せよ。 そうでない場合、A_i^{K_i} ≡ K_i(mod M_i) なる 2 × 10^{18} 以下の正整数 K_i をひとつ出力せよ。考えられるものが複数ある場合、どれを出力してもよい。

入力例 1

4
2 4
3 8
9 6
10 7


出力例 1

4
11
9
2


それぞれ、2^4 = 16 ≡ 4(mod 4)3^{11} = 177147 ≡ 11(mod 8)9^9 = 387420489 ≡ 9(mod 6)10^2 = 100 ≡ 2(mod 7) より、条件を満たします。

入力例 2

3
177 168
2028 88772
123456789 987654321


出力例 2

7953
234831584
471523108231963269


Score : 1400 points

Problem Statement

Process the Q queries below.

• You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.

Constraints

• 1 \leq Q \leq 100
• 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
• 1 \leq M_i \leq 10^9(1 \leq i \leq Q)

Inputs

Input is given from Standard Input in the following format:

Q
A_1 M_1
:
A_Q M_Q


Outputs

In the i-th line, print -1 if there is no integer K_i that satisfies the condition. Otherwise, print an integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i). If there are multiple solutions, any of them will be accepted.

Sample Input 1

4
2 4
3 8
9 6
10 7


Sample Output 1

4
11
9
2


It can be seen that the condition is satisfied: 2^4 = 16 ≡ 4 (mod 4), 3^{11} = 177147 ≡ 11 (mod 8), 9^9 = 387420489 ≡ 9 (mod 6) and 10^2 = 100 ≡ 2 (mod 7).

Sample Input 2

3
177 168
2028 88772
123456789 987654321


Sample Output 2

7953
234831584
471523108231963269