c - 有趣的 2 次幂 - 算法/数学(来自 Hackerrank ACM APC)

Question

我在最近的比赛中遇到了一个问题。
我无法找到解决方案，并且还没有针对该问题的社论。

Question Link

我在这里引用问题陈述也是为了以防链接不起作用。

找出大于或等于 A 且小于或等于 B (A<= n <=B) 的整数 n 的数量，并且 2^n 的 十进制表示以 n 结尾。

例如: 2^36 = 68719476736 以“36”结尾。

输入

第一行包含一个整数 T，即测试用例的数量。接下来是 T 行，每行包含两个整数 A 和 B。

约束

1 <= T <= 10^5

A<=B

A,B <= 10^150

输出

打印 T 行，每行包含相应测试用例的答案。

样本输入

2
36 36
100 500

样本输出

1
0

Answer 1

通常，您可以通过在输出中找到某种模式来尝试解决这些问题。我们的团队在比赛中接受了这个问题。我们的方法是在满足标准的值中找到一般模式。如果你打印前几个这样的数字，那么你会发现以下模式

    36
   736
  8736
 48736
948736

因此，948736 之后的下一个数字应该是 7 位数字，并且可以是 1948736、2948736、3948736、4948736、5948736、6948736、7948736、89489736 中的任何一个，因此检查下一个数字是有效的 9、9436。继续以这种方式，您可以支持自己获得所有 150 个号码。

但是这里有一个问题。通过将“1”附加到“9”，某些数字不会立即跟在前一个数字之后。为了解决这个问题，您现在可以开始附加从 10 到 99 的值，然后检查是否存在有效数字。如果仍然没有有效数字，则再次尝试附加从 100 到 999 的数字。

现在使用此技巧，您将获得满足问题中给出的标准的所有 137 个值，并轻松回答所有查询。例如，实现此功能的工作 Java 代码显示为 here 。它打印所有 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);
}