gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 10:49:10 25 4
gpt4 key购买 nike

我得到了一个大整数(位数最多可达 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 );
}

最佳答案

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

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

如果这对可被四整除的数字出现在位置 i-1i在字符串中,则有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;
}

关于java - 检查双整数子串的更快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35522081/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com