luogu#P11932. [CrCPC 2024] 平凡的数论题

[CrCPC 2024] 平凡的数论题

题目背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta B.

题目描述

给定非负整数序列 a,b,ca,b,c,长度分别为 a,b,c|a|,|b|,|c|。这里序列下标是 0-indexed 的。

l=max{ai,bi,ci}l=\max\{a_i,b_i,c_i\}

找到任意一个 [l+1,1019)\in [l+1,10^{19}) 的正整数 BB,使得 $\displaystyle \left(\sum_{0\le i\lt |a|} a_iB^i\right)\left(\sum_{0\le j\lt |b|} b_jB^j\right)=\sum_{0\le k\lt |c|} c_kB^k$ 成立。

数据保证,若存在正整数 Bl+1B\ge l+1 使得上式成立,则存在一个 [l+1,1019)\in [l+1,10^{19}) 的正整数 BB 使得上式成立。

输入格式

第一行,a+1|a|+1 个非负整数 a,aa1,aa2,,a0|a|,a_{|a|-1},a_{|a|-2},\ldots,a_0

第二行,b+1|b|+1 个非负整数 b,bb1,bb2,,b0|b|,b_{|b|-1},b_{|b|-2},\ldots,b_0

第一行,c+1|c|+1 个非负整数 c,cc1,cc2,,c0|c|,c_{|c|-1},c_{|c|-2},\ldots,c_0

数据保证 aa1,bb1,cc10a_{|a|-1},b_{|b|-1},c_{|c|-1}\neq 0

输出格式

如果存在 [l+1,1019)\in [l+1,10^{19})BB,直接输出;

否则输出一行一个 impossible\texttt{impossible}。

数据保证,若存在正整数 Bl+1B\ge l+1 使得上式成立,则存在一个 [l+1,1019)\in [l+1,10^{19}) 的正整数 BB 使得上式成立。

2 2 0
1 2
3 1 0 0
4
3 5 1 2
2 11 3
5 4 5 1 12 6
13
2 3 2
2 3 2
3 10 12 4
impossible

提示

  • 1a,b,c1031\le |a|,|b|,|c|\le 10^3
  • 0ai,bi,ci2300\le a_i,b_i,c_i\le 2^{30}
  • aa1,bb1,cc10a_{|a|-1},b_{|b-1|},c_{|c-1|}\neq 0
  • 若存在正整数 Bl+1B\ge l+1 使得上式成立,则存在一个 [l+1,1019)\in [l+1,10^{19}) 的正整数 BB 使得上式成立。