← 返回题目列表

AtCoder · iroha2019_day4_d

D. 城市震动,敌人数量不断增加

中文机器翻译题面 查看原题

配点 : \(600\) 点

苏托里

“到底是怎么回事......?”回家的路上,伊洛波酱开始时不时地聊天。“刚才那个怪物明显很奇怪。”“那东西在这个世界上可不好。”“就像个虫子......”

一声雷鸣般的咆哮回荡,仿佛打断了她的话语。 这次,这种情况发生了好几次。 我们交换了眼神,开始奔跑。

問題文

\(T\) 每个城镇都出现了敌人。

出现在(i)城市中的敌人排列成一行,呈垫状排列,原有格数介于(1)和(L_i之间)。 在城市中,你已经摧毁了超过\(0\)的敌方格子,敌人被摧毁的格子分成了几个部分。 棋子数为\(L\)的敌人会被边缘的\(i\)格消灭,然后分裂成两个敌人,格子分别为\(i-1\)和\(L-i\)(但格数为\(0\)的敌人会消失)。

然而,这个敌人分裂后会变得更强。 具体来说,当敌人的总战力按马p_n p_2 p_1斯数量划分为\(n\)部分时,敌方总战力为\(p_1乘以p_2\点\乘以p_n\)。

现在,据说在第\(i\)个城市,敌人的强度已经达到了\(2^{A_i}\)以上。请对于出现于\(T\)个城市的每个敌人,求出敌人最初可能所在的格子数有多少种。

制約

  • 所有输入均为整数
  • \(1≤T≤300\)
  • \(1≤L_i≤10^9,\ 0≤A_i≤10^9\)

入力

输入按以下格式给出。

\(T\)
\(L_1\) \(A_1\)
\(L_2\) \(A_2\)
:
\(L_T\) \(A_T\)

出力

输出第\(T\)行,并在第\(i\(1≤i≤T)\)行输出第\(i\)个城镇中出现的敌人的答案。


入力例

4
9 3
13 4
11 6
11235813 213455

出力例

3
5
0
10702177

第\(1\)个城镇中出现的敌人的原始方格数可以是\(7,8,9\)中的\(3\)个。

如果敌人被消灭,则满足以下条件(o表示该方格没有被破坏,x表示已损坏)。

  • 敌方方格的原始数量为\(7\): ooxoooo (敌人强度为\(8\))
  • 敌方方格的原始数量为\(8\): ooxooxoo (敌人强度为\(8\))
  • 敌人原来的方格数是\(9\): oooxoxooo (敌人强度为\(9\))

第\(2\)个城市中出现的敌人原始方格数有\(5\)种可能:\(9,10,11,12,13\)。

如果破坏以下列方式发生,则满足条件。

  • 敌人原来的方格数是\(9\): ooooxoooo (敌人强度为\(16\))
  • 敌方方格的原始数量为\(10\): ooxooxoooo (敌人强度为\(16\))
  • 敌方方格的原始数量为\(11\): oooxooooxoo (敌人强度为\(24\))
  • 敌方方格的原始数量为\(12\): oooooooooxoo (敌人强度为\(18\))
  • 敌方方格的原始数量为\(13\): ooooxoooooooo (敌人强度为\(32\))

第\(3\)个城镇中出现的敌人的原始方格数可以为\(0\)。


解説

解説