Сумма самых больших нечетных делителей первых n чисел
Я работал над topcoder недавно, и я наткнулся на этот вопрос, который я не могу вполне сделать, понимают. Вопрос состоит в том, чтобы найти F (n) = f (1) +f (2) +.... +f (n) для данного "n" таким образом, что f (n) является самым большим нечетным делителем для n. Существует много тривиальных решений для ответа; однако, я нашел это решение очень интригующим.
int compute(n) {
if(n==0) return 0;
long k = (n+1)/2;
return k*k + compute(n/2);
}
Однако я не вполне понимаю, как получить рекурсивное отношение из проблемного оператора, такого как это. Кто-то мог выручить?
3 ответа
Думаю, они пытаются использовать следующие факты:
- f (2k + 1) = 2k + 1, т.е. наибольший нечетный делитель нечетного числа - это само число.
- f (2k) = f (k). т.е. наибольший нечетный делитель четного числа 2m совпадает с наибольшим нечетным делителем числа m.
- Сумма первых k нечетных чисел равна k ^ 2.
Теперь разделите {1,2, ..., 2m + 1} на {1,3,5,7, ...} и {2,4,6, ..., 2m} и попробуйте применить приведенные выше факты.
если бы это была Java, я бы сказал:
import java.util.*;
int sum_largest_odd_factors (int n){
ArrayList<Integer> array = new ArrayList();//poorly named, I know
array.add(1);
for(int j = 2; j <= n; j++){
array.add(greatestOddFactor(j));
}
int sum = 0;
for(int i = 0; i < array.size(); i++){
sum += array.get(i);
}
return sum;
}
int greatestOddFactor(int n){
int greatestOdd = 1;
for(int i = n-((n%2)+1); i >= 1; i-=2){
//i: starts at n if odd or n-1 if even
if(n%i == 0){
greatestOdd = i;
break;
//stop when reach first odd factor b/c it's the largest
}
}
return greatestOdd;
}
Это, по общему признанию, утомительная и, вероятно, O(n^2) операция, но она будет работать каждый раз. Перевод на C++ я оставлю на ваше усмотрение, поскольку Java и J - единственные языки, с которыми я могу работать (да и то на низком уровне). Мне интересно, какие гениальные алгоритмы могут придумать другие люди, чтобы сделать это намного быстрее.
Я не могу понять, как этот алгоритм может работать для описанной вами проблемы. (Я предполагаю, что «N» и «n» относятся к одной и той же переменной).
Дано n = 12.
Наибольший нечетный делитель равен 3 (остальные - 1, 2, 4, 6 и 12)
F (12), следовательно, f (1) + f (2) + f (3) или 1 + 1 + 3 или 5.
Используя этот алгоритм:
k = (12 + 1) / 2 или 6
и мы возвращаем 6 * 6 + f (6), или 36 + некоторое число, которое не будет отрицательным 31.