問題文

直径 200 mmのウェーハ（円盤状の金属の薄い板）と、直径 300 mmのウェーハがあります。 この 2 つのウェーハから、縦横の長さが K mmの正方形のチップを作成しようとしています。

垂直方向・水平方向の 2 方向に、 円の端から K mmずつ等間隔にウェーハを切断していくことで、正方形のチップを作成していきます。

この時、直径 200 mmのウェーハで取れるチップの数と、直径 300 mmのウェーハから取れるチップの数を求めてください。

例えば、 K=20 の時、以下のようにチップを作成することができます。直径 200 mmのウェーハからは 60 個、直径 300 mmのウェーハからは 145 個のチップを取ることができます。

K=20の時の、ウェーハからチップを取った時の図

制約

• 4 ≦ K ≦ 50
• K は 200 および 300 の約数である。つまり、どちらのウェーハについても、円の端から端まで、あまりなしで等間隔に切断することが可能である。

入力例 1

20

出力例 1

60 145

• 問題文中の例で与えられた入力です。

入力例 2

5

出力例 2

1176 2700

入力例 3

50

出力例 3

4 16

問題文

高橋君は N 台のロボットを持っています。ロボットには番号 1, 2, ..., N がついています。

ロボットにはそれぞれ正整数が 1 つ書かれており、番号 i のロボットには a_i が書かれています。

番号 i のロボットは、正整数 X, Y を渡すと、{\rm gcd}(X, a_i) = {\rm gcd}(Y, a_i) ならば「似てる」、そうでないならば「似てない」と言います。なお、この問題では {\rm gcd}(X, Y) は X と Y の最大公約数とします。

正整数 X, Y について、N 台のロボット全てが「似てる」と言った時、X と Y はそっくりさんだとすることにします。

正整数 Z が与えられるので、Z とそっくりさんな数のうち、もっとも小さいものを求めてください。

制約

• 1 ≦ N ≦ 100,000
• 1 ≦ Z, a_i ≦ 10^{18}

入力例 1

3 12
2 6 9

出力例 1

6

• {\rm gcd}(6, 2) = {\rm gcd}(12, 2) = 2
• {\rm gcd}(6, 6) = {\rm gcd}(12, 6) = 6
• {\rm gcd}(6, 9) = {\rm gcd}(12, 9) = 3

であるため、6 と 12 はそっくりさんであり、 また 6 より小さくて 12 とそっくりさんな数は存在しないため、6 が答えとなります。

入力例 2

10 1000000007
1 2 3 4 5 6 7 8 9 10

出力例 2

1

入力例 3

2 1000000000000000000
1000000000000000000 1000000000000000000

出力例 3

1000000000000000000

問題文

N 頂点 M 辺の有向グラフが与えられます。 頂点には 1, 2, ..., N と番号が付いており、 i 番目の辺は頂点 a_i から頂点 b_i へ張られる、長さ c_i の辺です。 また、このグラフは強連結、つまりすべての i, j(1 ≦ i, j ≦ N) について、 頂点 i から頂点 j へのパスが存在します。

あなたはこのグラフの辺を 1 本だけ選び、長さを好きに変える事が出来ます。 なお、元の長さと同じ長さにしても良いです。

グラフを、どのサイクルを選んでも長さが 0 となるようにできるかを判定してください。

グラフから 2 本以上辺を選んだ時(辺を M 本、d_1, d_2, ..., d_M 番目の辺を選んだとします)、以下の条件を満たすならば、この選んだ辺たちをグラフのサイクルと呼びます。

• i = 1, 2, ..., M-1 について、b_{d_i} = a_{d_{i+1}}
• a_{d_1} = b_{d_M} (11:26)修正しました
• i ≠ j ならば、a_{d_i} ≠ a_{d_j} (11:22)修正しました

サイクルの長さとは、選んだ辺たちの長さの総和の事を指します。

制約

• 入力は全て整数
• 2 ≦ N ≦ 300
• 1 ≦ M ≦ N^2 - N
• 1 ≦ a_i, b_i ≦ N
• |c_i| ≦ 10^9
• a_i ≠ b_i
• すべての 1 ≦ i, j ≦ M について、i ≠ j ならば a_i ≠ a_j もしくは b_i ≠ b_j
• 与えられるグラフは強連結、つまりすべての 1 ≦ i, j ≦ N について、頂点 i から頂点 j へのパスが存在する

入力例 1

3 3
1 2 1
2 3 2
3 1 3

出力例 1

Yes

どれかの辺の長さを 1+2+3 = 6 減らせばよいです。

入力例 2

4 5
1 2 1
2 3 2
3 1 2
2 4 3
4 1 3

出力例 2

No

入力例 3

4 5
1 2 1
2 3 -2
3 1 2
2 4 -3
4 1 3

出力例 3

Yes

1 番目の辺の長さを 0 にすればよいです。

問題文

N 頂点の木が与えられます。 頂点には番号 1, 2, ..., N がついており、i 番目の辺は頂点 a_i, b_i をつないでいます。

木の頂点に整数 1, 2, ..., N をそれぞれ 1 個ずつ書き込むことを考えます。 頂点 i に書き込んだ値を c_i とします。

ただし、頂点 u, v が隣り合っている、つまり辺 (u, v) が存在するならば、 |c_u - c_v| ≦ 2 を満たしていないといけません。(10:53)変数名を修正しました

このような書き込み方は何通りあるでしょうか、1000000007 = 10^9 + 7 で割った余りを求めてください。

制約

• 1 ≦ N ≦ 50
• 1 ≦ a_i, b_i ≦ N
• 入力は木になっている

入力例 1

5
1 2
1 3
1 4
1 5

出力例 1

24

頂点 1 に 3 を書き込む必要があります。

入力例 2

6
1 2
1 3
1 4
1 5
1 6

出力例 2

0

入力例 3

4
1 2
2 3
3 4

出力例 3

12

入力例 4

7
1 3
2 3
4 3
5 4
5 6
5 7

出力例 4

48

問題文

高橋君は N 頂点からなる木のぬいぐるみを持っています。 頂点には番号 1, 2, ..., N がついています。

i 番目の辺は頂点 a_i, b_i をつないでおり、長さは 1 です。

{\rm dist}(u, v) を頂点 u から頂点 v への最短距離と定義します。すると木の直径は {\rm max}_{1 ≦ u < v ≦ N}({\rm dist}(u, v)) となります。

青木君はこのぬいぐるみに対して、辺を 1 本選んでその長さを 1 増やす、というイタズラを何回か行いました。 イタズラの回数は K_1, K_2, ..., K_Q のどれかであることが分かっています。

また、青木君は直径の短い木のほうが好きなので、イタズラを全て終えた後の木の直径ができる限り短くなるように操作を行ったことが分かっています。

イタズラの回数が K_1, K_2, ..., K_Q の場合それぞれについて、イタズラを全て終えた後の木の直径を求めてください。

制約

• 3 ≦ N ≦ 200,000
• 1 ≦ a_i, b_i ≦ N
• 入力は木になっている
• 1 ≦ Q ≦ 200,000
• 0 ≦ K_1 < K_2 < ... < K_Q ≦ 10^{18}

入力例 1

4
1 2
1 3
1 4
10
0 1 2 3 4 5 6 7 8 9

出力例 1

2
3
4
4
5
6
6
7
8
8

入力例 2

9
1 4
2 4
3 4
4 5
5 6
6 7
7 8
8 9
10
0 1 2 3 4 5 6 7 8 9

出力例 2

6
7
7
7
8
8
8
9
9
9

入力例 3

6
6 3
3 4
3 2
3 1
1 5
31
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

出力例 3

3
4
4
4
5
6
6
6
7
8
8
8
9
10
10
10
11
12
12
12
13
14
14
14
15
16
16
16
17
18
18