结果总数错误？ [英] Number of consectuive sums error?
问题描述
我正在研究一个取整数的程序，并找到整数所具有的连续和的组合数：
I am working on a program that takes an integer and finds the number of combinations of consecutive sums that the integer has:
数字13可以表示为连续正
整数6 + 7的总和。十四可以表示为2 + 3 + 4 + 5，也是连续正整数的总和
。有些数字可以用多种方式表示为
连续正整数的总和。对于
的例子，25是12 + 13，也是3 + 4 + 5 + 6 + 7.
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的数量。所以我写了一个程序来查找奇数因子的数量，在某些情况下我的答案仍然是错误的。有什么见解吗？
I researched and read that it's the number of odd factors minus one. So I wrote a program that finds the number of odd factors and my answer is still wrong in certain cases. Any insight?
代码似乎工作正常，但是由于Timeout导致崩溃可能是由于优化错误。
Code seems to work fine but there is a crash due to Timeout which is probably due to optimization error.
可能输入大小的约束是
1到10 ^（12）
The constraints for possible input size is 1 to 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();
}
}
这就是我目前所拥有的
推荐答案
由于我回复的帖子是重复的，我也在这里复制了我的答案。
让我们试着找一个伪优化方法来解决您的问题：
您需要做的是在素因子中分解您的数字。
例如，如果你选择 1200 ：
1200 = 2 * 2 * 2 * 2 * 3 * 5 * 5 = 1 * 2 ^ 4 * 3 ^ 1 * 5 ^ 2
您可以分析如何利用这些素因子得到奇怪的因素。快速分析会告诉您：
You can then analyze how you could get odd factors with those prime factors. A quick analyze will tell you that :
- 奇数*奇数=奇数
- 奇数*偶数=偶数
- 偶数*偶数=偶数
随着记住，让我们找到我们得到的所有因素奇数*奇数：
With that in mind, let's find all the factors we get with odd * odd :
- 1 * 1 = 1
- 3 * 1 = 3
- 5 * 1 = 5
- 5 * 3 = 15
- 5 * 5 = 25
- 5 * 5 * 3 = 75
- 1 * 1 = 1
- 3 * 1 = 3
- 5 * 1 = 5
- 5 * 3 = 15
- 5 * 5 = 25
- 5 * 5 * 3 = 75
快速查找这些组合而不全写它们的方法是加1方法：将每个素数奇数因子的出现次数加1，然后将它们相乘：
A quick way to find these combinations without writing them all is the "plus 1 method" : add 1 to the number of occurences of each prime odd factor, and multiply them together :
我们发现 1200 = 1 * 2 ^ 4 * 3 ^ 1 * 5 ^ 2 ，我们可以这样做：
We found that 1200 = 1 * 2^4 * 3^1 * 5^2, so we can do :
- （数字3+ 1）（数字5+ 1）=
（1 + 1）（2 + 1）= 6
- ("number of 3" + 1) ("number of 5" + 1) =
(1 + 1) ( 2 + 1) = 6
有数字1200的6个奇数因子，如你所述，从中删除1这个数字可以得到1200具有的连续总和的组合数量：
- 6 - 1 = 5 < - 呜呜！终于得到了结果！
- 6 - 1 = 5 <-- woohoo ! finally got the result !
现在，让我们来看看代码。 我们想要的是地图，关键是主要因素，价值是他们出现的次数：
Now, let's look at the code. What we want to have is a Map, the keys being the prime factors and the values being the number of their occurences :
/*
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;
}
有了这个，让我们尝试打印地图中包含的数字 1200 ：
With that, let's try to print what the map contains for number 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
完了！随便问你是否理解不了什么！
b
注意：我尝试使用Integer可以处理的最大值我的程序，我的程序继续花费不到一秒钟，对我来说似乎很快。它可能会更快，但是你可以找到这个代码的最优化版本！
Finished ! feel free to ask if you did not understand something !
Note : I tried my program with the max value Integer can handle and it took less than one second for my program to proceed, which seems pretty fast to me. It could probably be faster though, it's up to you to find the most optimized version of this code !
这篇关于结果总数错误？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
