Polynomial Division (Easy)

2 secs 1024 MB
magurofly's icon magurofly

問題文

NN 次多項式 A(x)=aNxN++a1x+a0A(x) = a_N x^N + \cdots + a_1 x + a_0 と、 MM 次多項式 B(x)=bMxM++b1x+b0B(x) = b_M x^M + \cdots + b_1 x + b_0 が与えられます。

A(x)A(x)B(x)B(x) で割った商 Q(x)Q(x) と 余り R(x)R(x) を計算してください。

制約

  • 0N,M1000 \le N, M \le 100
  • 0ai,bj1090 \le a_i, b_j \le 10^9
  • aN,bM,B(x)0a_N, b_M, B(x) \ne 0
  • 入力はすべて整数

入力

N M
a_N ... a_1 a_0
b_M ... b_1 b_0

出力

11 行目に Q(x)Q(x)R(x)R(x) の次数、 22 行目に Q(x)Q(x) の係数を 109+710^9 + 7 で割ったあまり、 33 行目に R(x)R(x) の係数を 109+710^9 + 7 で割ったあまりを次数が高い順に出力してください。

K L
q_K ... q_1 r_0
r_L ... r_1 r_0

入出力例1

入力例1
2 1
1 3 3
1 2
出力例
1 0
1 1
1

x2+3x+3x^2 + 3x + 3x+2x + 2 で割ると、商は x+1x + 1 、 余りは 11 になります。

入出力例2

入力例2
2 1
1 0 1000000006
1 1
出力例2
1 0
1 1000000006
0

x21x^2 - 1x+1x + 1 で割ると、商は x1x - 1 、 余りは 00 になります。

入出力例3

入力例3
2 1
1 3 2
2 1
出力例3
1 0
500000004 250000003
750000006

x2+3x+2x^2 + 3x + 22x+12x + 1 で割ると、 商は 12x+54\frac{1}{2} x + \frac{5}{4} 、 余りは 34\frac{3}{4} になります。

Submit


Go (1.21)