All geek questions in one place

Interesting Abilities 2 - Algorithm / Math (by Hackerrank ACM APC)

I ran into the challenge of a recent competition. I could not find a solution, and the editorial issue on this issue is not yet available.

Question Link

I quote the problem statement here also in case the link doesn't work.

Find the number of integers n that are greater than or equal to A and less than or equal to B (A <= n <= B), and the decimal representation 2 ^ n ends in n .

Example: 2 ^ 36 = 68719476736, which ends with "36".

INPUT

The first line contains an integer T ie the number of test cases. T, each of which contains two integers A and B.

Limitations

1 <= T <= 10^5

A<=B

A,B <= 10^150

OUTPUT

Print T lines, each of which contains the answer to the corresponding test file.

Input example

2
36 36
100 500


1
0
+4
5

, , - . , . , , . ,

    36
   736
  8736
 48736
948736

, 948736 7 1948736, 2948736, 3948736, 4948736, 5948736, 6948736, 7948736, 8948736, 9948736. , , , , , , 150 .

. , , "1" "9". , 10 99 , . - , 100 999.

, , 137 , , , . , Java-, , . 137.

import java.io.*;
import java.math.*;
import java.util.*;

class Solution
{ 

    public static void main(String[] args)throws java.lang.Exception{
        new Solution().run();
    }

    void run()throws java.lang.Exception{
        BigInteger[] powers = new BigInteger[152];
        powers[0] = one;
        for(int i=1; i<=150; i++){
            powers[i] = powers[i-1].multiply(ten);
        }
        BigInteger[] answers = new BigInteger[152];
        answers[2] = BigInteger.valueOf(36);
        answers[3] = BigInteger.valueOf(736);

        int last = 3;
        for(int i=4; i<=150; i++){
            int dif = i-last;
            BigInteger start = ten.pow(dif-1);
            BigInteger end = start.multiply(ten);
            while(start.compareTo(end) < 0){
                BigInteger newVal = powers[last].multiply(start);
                newVal = newVal.add(answers[last]);
                BigInteger modPow = pow(two, newVal, powers[i]);
                if(modPow.equals(newVal)){
                    answers[i] = newVal;
                    System.out.println(answers[i]);
                    last = i;
                    break;
                }
                start = start.add(one);
            }
        }
    }


    BigInteger pow(BigInteger b, BigInteger e, BigInteger mod){
        if(e.equals(zero)){
            return one;
        }
        if(e.mod(two).equals(zero)){
            BigInteger x = pow(b, e.divide(two), mod);
            x = x.multiply(x).mod(mod);
            return x;
        }else{
            BigInteger x = pow(b, e.divide(two), mod);
            x = x.multiply(x).mod(mod);
            x = x.multiply(two).mod(mod);
            return x;
        }
    }

    BigInteger ten = BigInteger.valueOf(10);
    BigInteger zero = BigInteger.ZERO;
    BigInteger one = BigInteger.ONE;
    BigInteger two = BigInteger.valueOf(2);
}
+3

, , , . , 1000000, :

36
736
8736
48736
948736

, : . , . : , 150 , 9 , .

- - .

, , , , . , . , .

: , ( - ). , , v3ga , 75353432948736, , "" , . - 0, .

:

:, a 1 a 2... a n - , n - 3, 2... a n.

: 2 a 1 a 2... a n= 2 a 1 * 10 n - 1 * 2 a 2 a 2... a n >

, 2 a 1 * 10 n - 1 * 2 a 2 a 2... a n 2 a 2 a 2... a n 10 n-1.

, 2 a 1 * 10 n - 1 * 2 a 2 a 2... a n - 2 a 2 a 2... a n 10 n-1.

2 a 1 * 10 n - 1 * 2 a 2 a 2... a n - 2 a 2 a 2... a n = 2 a 2 a 2... a n * (2 a 1 * 10 n - 1 - 1) a 2 a 2... a n , n-1 .

, , , 10 n-1 , 5 n-1 2 a 1 * 10 n - 1 - 1.
:

2 phi (5 n-1)= 1 ( 5 n-1).

phi (5 n-1) = 4 * (5 n-2) n >= 3 4 * (5 n-2) 1 * 10 n - 1 ( 10 n - 1).

, 2 a 1 * 10 n - 1 1 5 n-1 5 n-1 2 a 1 * 10 n - 1 - 1.

, 10 n-1 2 a 2 a 2... a n * (2 a 1 * 10 n - 1 - 1), n - 1 2 a 1 a 2 a 2... a n 2 a 2 a 3 a 4... a n .

1 a 2 a 2... a n n 2 a 1 a 2 a 2... a n - 1 a 2 a 2... a n, n-1 2 a 2 a 3 a 4... a n 2 a 3 a 4... a n , , 2 a 3 a 4... a n . QED.

, . , , .

+8

. , 36 500 python...
: 2 ^ 36 : 36, - 736, 736. 2 ^ 736 736, - 8376...

: 36, 736, 8736, 48736, 948736...

BigInt ++. , , , . . : Ideone it!

def powm(i):
j = 10
a = 1
while i:
    if i % 2:
        a = a * j
    i /= 2
    j *= j
return a


def power(n, i):
    m = powm(i)
    y = 1
    x = 2
    while n:
        if n % 2 == 1:
            y = y * x % m
        x = x * x % m
        n /= 2
    return y

mylist = []
mylist.append(power(36, 2))
n = mylist[0]
print(n)
for i in range(3, 170):
    p = power(n, i)
    print p
    if p != n:
        mylist.append(p)
        n = p

t = input()
while t:
    x = raw_input().split(" ")
    a = int(x[0])
    b = int(x[1])
    i = 0
    #while i <= 150:
        #print mylist[i]
        #i += 1
#print power(8719476736,14)

while mylist[i] < a:
    i += 1
ans = 0
while mylist[i] <= b:
    i += 1
    ans += 1
print ans
t -= 1
+2

20 . , n 1 2. , n .

2 ^ 1 = 2
2 ^ 21 = 2097152
2 ^ 101 = 2535301200456458802993406410752

2 ^ 2 = 4
2 ^ 22 = 4194304
2 ^ 42 = 4398046511104

:

2 ^ 14 = 16384
2 ^ 16 = 65536

2 ^ 34 = 17179869184
2 ^ 36 = 68719476736

n 14 + 20x 16 + 20x, , . .

0

. , -, . n A B:
 1. k, n. O (logn)
 2. 2 ^ n (mod 10 ^ k) , n. O (n). (, O (n) )


, n. 2 ^ n (mod 10 ^ k), 2 ^ (n + 1) (mod 10 ^ k) . , .

- 2 .

0

Source: https://habr.com/ru/post/1534238/

More articles:


All Articles