java - 检查双整数子串的更快方法

Question

我得到了一个大整数(位数最多可达 300000)。我应该找出整数的多少个子串可以被 4 整除。 我的代码很慢。任何使它更快的建议都值得赞赏。

public static void solve() throws IOException {
  String s = (new BufferedReader (new InputStreamReader (System.in))).readLine();
  int l = s.length(), d = 0; // d is number of substrings divisible by 4
  BigInteger f = new BigInteger("4");
  for(int i = 0; i < l; i++) {
    for(int j = i + 1; j <= l; j++) {
      String te = (s.substring(i,j)).replaceFirst("^0+(?!$)", ""); //regex used for leading zeros
      if( te.charAt(te.length()-1) == '3' || te.charAt(te.length()-1) == '5' || te.charAt(te.length()-1) == '7' || te.charAt(te.length()-1) == '9' )
        continue;
      else {
        BigInteger temp = new BigInteger(te);
        if ( (temp.mod(f)).toString().equals("0") )
          d++;
      }
    }
   }
  System.out.println( d );
}

Answer 1

如果一个整数可以被 4 整除，则该数小于 10 且以 0、4 或 8 结尾；或最后两位数能被 4 整除。

如果字符串的第一个字符本身可以被四整除，那么它就是您要计算的子字符串之一。

如果这对可被四整除的数字出现在位置 i-1和 i在字符串中，则有i + 1如果数字以偶数开头，则带有该后缀的子串，以及 i如果数字以奇数开头，则为子字符串。

因此，您可以按如下方式计算可被 4 整除的子串的数量:

int v = 0;
long cnt = 0;
for (int i = 0; i < s.length(); ++i) {
  int w = Character.digit(s.charAt(i), 10);
  if ((v * 10 + w) % 4 == 0) {
    cnt += i;
  }
  if (w % 4 == 0) {
    ++cnt;
  }
  v = w;
}