简单分析¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
实验室要估算快速幂程序调用乘法模块的次数。指数可能很长，研究员只提供它的二进制表示，请帮助完成这项统计。
(本故事由GPT-6重写)
形式化问题描述¶
分析下面的完整伪代码。所有变量表示任意精度整数，multiply(x,y,m) 返回 \(xy\bmod m\) .只统计 multiply 的调用次数，不统计它内部的基本运算。
初始指数为非负整数 \(e\) ，执行前 index = e .辅助参数满足：modulus 是质数，base 与 modulus 互质，并且 \(0\le e<\text{modulus}-1\) .
result = 1
index = index mod (modulus - 1)
while index > 0:
if index mod 2 == 1:
result = multiply(result, base, modulus)
index = floor(index / 2)
if index > 0:
base = multiply(base, base, modulus)
return result
每个输入字符串表示一个初始指数。辅助参数不作为输入；在上述保证下，调用次数仅由指数决定。前导零不改变指数。注意右移后指数为零时，不再执行一次平方。
输入格式¶
第一行一个非负整数 \(Q\) ，表示查询数。接下来 \(Q\) 行，每行一个非空字符串，仅由 0 和 1 组成，表示无符号二进制整数。
输出格式¶
输出 \(Q\) 行，每行一个整数，表示对应指数导致的 multiply 调用次数。\(Q=0\) 时输出为空。
样例¶
样例 1¶
输入¶
5
0
10011
1111
1
1100
输出¶
0
7
7
1
5
样例 2¶
输入¶
4
0000
0001
00100
00101
输出¶
0
1
3
4
样例 3¶
输入¶
3
10
100000
111111
输出¶
2
6
11
样例解释¶
第一组中，10011 的数值为 \(19\) .循环处理的指数依次为 \(19,9,4,2,1\) ，条件乘法调用三次，平方调用四次，共七次。0 不进入循环；1 只进行一次条件乘法。第二组说明前导零不增加调用次数。
数据范围与保证¶
所有数据满足：\(0\le Q\le2.1\times10^6\) ，每个字符串非空，所有字符串的长度之和不超过 \(2.1\times10^6\) .每个指数均满足形式化描述中的辅助参数保证。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |