Simple Analysis¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
On the target judge, multiply the reference program's largest per-case median time by \(2\) and round up to a multiple of \(0.5\) seconds. See the reference environment.
Story¶
A laboratory is estimating how many calls a binary-exponentiation routine makes to its multiplication module. The exponent may be very long and is supplied in binary.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
Analyze the complete pseudocode below. All variables represent arbitrary-precision integers. The function multiply(x,y,m) returns \(xy\bmod m\) . Count calls to multiply , rather than elementary operations inside that function.
The initial exponent is a nonnegative integer \(e\) , with index = e before execution. The auxiliary parameter modulus is prime, base is coprime to it, and \(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
Each input string represents an initial exponent. The auxiliary parameters are not part of the input; under these guarantees the count depends only on the exponent. Leading zeros do not change it. Notice that no squaring call is made after the exponent becomes zero.
Input Format¶
The first line contains a nonnegative query count \(Q\) . Each of the next \(Q\) lines contains a nonempty string of 0 and 1 , representing an unsigned binary integer.
Output Format¶
Print \(Q\) lines, each containing the number of multiply calls for that exponent. If \(Q=0\) , produce no output.
Examples¶
Example 1¶
Input¶
5
0
10011
1111
1
1100
Output¶
0
7
7
1
5
Example 2¶
Input¶
4
0000
0001
00100
00101
Output¶
0
1
3
4
Example 3¶
Input¶
3
10
100000
111111
Output¶
2
6
11
Example Explanation¶
In the first example, 10011 represents \(19\) . The loop processes \(19,9,4,2,1\) : three conditional multiplications and four squarings, for seven calls. Exponent 0 never enters the loop; 1 makes one conditional multiplication. The second example shows that leading zeros do not add calls.
Constraints and Guarantees¶
All inputs satisfy \(0\le Q\le2.1\times10^6\) . Every string is nonempty and their total length is at most \(2.1\times10^6\) . Each exponent has auxiliary parameters satisfying the guarantees in the formal statement.
| Score | Additional conditions |
|---|---|
| 100% | None |