结果总数错误？
我正在研究一个取整数的程序，并找到整数具有的连续和的组合数：
数字13可以表示为连续正整数6 + 7的总和。十四可以表示为2 + 3 + 4 + 5，也是连续正整数的总和。 有些数字可以表示为多个连续正整数的总和。 例如，25是12 + 13并且也是3 + 4 + 5 + 6 + 7。
我研究并读到它是奇数因子减去1的数量。 所以我写了一个程序来查找奇数因子的数量，在某些情况下我的答案仍然是错误的。 任何见解？
代码似乎工作正常但由于Timeout导致崩溃可能是由于优化错误。
可能的输入大小的约束是1到10 ^（12）
以下代码复制自alfasin的答案如下：
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(); } } 这就是我现在拥有的
由于我回答的post是重复的，我也在这里复制了我的答案。
让我们尝试找到一种伪优化方法来解决您的问题：
你需要做的是在主要因素中分解你的数字 。
例如，如果你拿1200 ：
1200 = 2*2*2*2*3*5*5 = 1 * 2^4 * 3^1 * 5^2
然后，您可以分析如何利用这些素因子获得奇数因子 。 快速分析会告诉您：
- 奇数*奇数=奇数
- 奇数*偶数=偶数
- 甚至*偶数=偶数
考虑到这一点，让我们找到奇数*奇数得到的所有因素：
- 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 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 oddPrimeFactors(int number) { int n = number; Map 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; }
有了它，让我们尝试打印地图包含的数字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可以处理的最大值我的程序，并且我的程序继续花费不到一秒钟，这对我来说似乎相当快。 它可能会更快，但是你可以找到这个代码的最优化版本！
以下是我们在评论部分中讨论的优化，请将评论视为标记：
static int consecutive(long num) { while (num % 2 == 0) num /= 2; // 1st opt. return consecutiveHelper(num)-1; } public static int consecutiveHelper(long num) { long factorNumber = 1; int count = 0; while(factorNumber <= num / 2) { // 2nd opt. if(num % factorNumber == 0) { count++; } factorNumber += 2; // 3rd opt. } if (num % 2 != 0) { count++; } return count; }
UPDATE
我设法通过使用Java 8 Stream接口并行并行运行来减少大数字（10 ^ 12）的运行时间约50％：
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(); }
也就是说，当您处理较小的数字时，并行将更加昂贵。 如果你希望你的答案是最佳的，你应该使用两种方法：对于较小的数字使用第一种，而对于较大的数字使用后者。