java - 连续总和错误的次数？

Question

我正在开发一个程序，该程序接受一个整数并查找该整数具有的连续和的组合数量:

The number 13 can be expressed as a sum of consecutive positive integers 6 + 7. Fourteen can be expressed as 2 + 3 + 4 + 5, also a sum of consecutive positive integers. Some numbers can be expressed as a sum of consecutive positive integers in more than one way. For example, 25 is 12 + 13 and is also 3 + 4 + 5 + 6 + 7.

我研究并读到它是奇数因数减一。所以我写了一个程序来查找奇数因数的数量，但在某些情况下我的答案仍然是错误的。有什么见解吗？

代码似乎工作正常，但由于超时而崩溃，这可能是由于优化错误造成的。

可能的输入大小的约束是1 到 10^(12)

以下代码复制自alfasin's answer如下:

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


  static long consecutive(long num) {
    while (num % 2 == 0) num /= 2;
    return  consecutiveHelper(num);
}

public static long consecutiveHelper(long num) {
    return LongStream.rangeClosed(3, (num / 2)).parallel().filter(x -> x % 2 != 0).map(fn -> (num % fn == 0) ? 1 : 0).sum();
}
        public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        final String fileName = System.getenv("OUTPUT_PATH");
        BufferedWriter bw = null;
        if (fileName != null) {
            bw = new BufferedWriter(new FileWriter(fileName));
        }
        else {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        int res;
        long num;
        num = Long.parseLong(in.nextLine().trim());

        res = consecutive(num);
        bw.write(String.valueOf(res));
        bw.newLine();

        bw.close();
    }
}

这就是我现在拥有的

Answer 1

由于我回答的帖子重复，所以我也将我的答案复制到这里。

让我们尝试找到一个伪优化方法来解决您的问题:

您需要做的就是将您的数字分解为质因数。

例如，如果您选择1200:

1200 = 2*2*2*2*3*5*5 = 1 * 2^4 * 3^1 * 5^2

然后您可以分析如何用这些质因数得到奇数因数。快速分析会告诉您:

• 奇数 * 奇数 = 奇数
• 奇数 * 偶数 = 偶数
• 偶*偶=偶

考虑到这一点，让我们找出通过 odd * odd 得到的所有因子:

• 1 * 1 = 1
• 3 * 1 = 3
• 5 * 1 = 5
• 5 * 3 = 15
• 5 * 5 = 25
• 5 * 5 * 3 = 75

无需全部写出这些组合的快速方法是“加 1 方法”:将每个素数奇因数出现的次数加 1，然后将它们相乘:

我们发现1200 = 1 * 2^4 * 3^1 * 5^2，所以我们可以这样做:

• ("3 的数量"+ 1) ("5 的数量"+ 1) = (1 + 1) ( 2 + 1) = 6

数字 1200 有 6 个奇因数，正如您所说，从该数字中删除 1 即可得到 1200 的连续和的组合数:

• 6 - 1 = 5 <-- 哇哦!终于得到结果了!

<小时/>

现在，让我们看一下代码。 我们想要的是一个Map，键是质因数，值是它们出现的次数:

/*
    If number is odd,
    find the number in the keys and add 1 to its value.
    If the number is not in the keys, add it with value = 1.
 */
public static void addValue(Map<Integer, Integer> factors, int i) {
    if(i % 2 != 0) {
        int count = factors.containsKey(i) ? factors.get(i) : 0;
        factors.put(i, ++count);
    }
}

/*
    Classic algorithm to find prime numbers
 */
public static Map<Integer, Integer> oddPrimeFactors(int number) {
    int n = number;
    Map<Integer, Integer> factors = new HashMap<>();
    for (int i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            addValue(factors, i);
            n /= i;
        }
    }

    if(n > 1) addValue(factors, n);
    return factors;
}

接下来，让我们尝试打印 map 中包含的数字 1200 的内容:

public static void main(String[] args) {
    int n = 1200;

    System.out.println(oddPrimeFactors(n));
}

$n : {3=1, 5=2}

好!现在让我们用我们之前开发的方法来完成程序:

public static int combinations = 1;

public static void main(String[] args) {
    int n = 1200;

    oddPrimeFactors(n).forEach((key, value) -> combinations *= (value + 1));
    combinations--;

    System.out.println(combinations);
}

$combinations = 5

完成的 !如果您有不明白的地方，请随时询问!

注意:我用 Integer 可以处理的最大值尝试了我的程序，我的程序只用了不到一秒的时间就可以继续，这对我来说似乎相当快。不过它可能会更快，这取决于您找到此代码的最优化版本!