首页 > 代码库 > 网易2017年校招笔试题 最大的奇约数
网易2017年校招笔试题 最大的奇约数
题目：
定义函数f(x)为x的最大奇数约数，x为正整数，例如f(44) = 11.
现在给出一个N,需要求出f(1) + f(2) + f(3) + ... + f(N)
例如： N = 7
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 7 = 21.
分析：
奇数的最大约数是自身， 偶数的最大约数是是除去所有偶因子之后的那个奇数。所以直观的思路就是挨个遍历一遍加起来。
代码：
1 #include <iostream> 2 using namespace std; 3 int main() { 4 long long N; 5 cin >> N; 6 long long result = 0; 7 for (long long i = 1; i <= N; ++i) { 8 int temp = i; 9 while (temp % 2 == 0) {10 temp /= 2;11 }12 result += temp;13 }14 cout << result << endl;15 return 0;16 }
然而， N的取值范围时10^10，所以O(n)的算法是超时的。
考虑优化，设sum(i) = f(1) + f(2) + ... + f(i)；
求sum(i)的过程中，所以f(i), i 为奇数可以直接求，就是 i 本身。
问题就是求所有f(i), i为偶数的和。
因为是最大奇约数，所以f(2k) = f(k)，所以f(2) + f(4) + ... + f(2k) = f(1) + f(2) + ... + f(k);
所以
sum(i) = sum (i / 2) + 1 + 3 + ... + i - 1 （i 为偶数）
= sum (i - 1) + i （i 为奇数）
时间复杂度O(logn)，可以解决。
1 #include<iostream> 2 using namespace std; 3 long long sum(long long n) { 4 if (n == 1) { 5 return 1; 6 } 7 if (n % 2 == 0) { 8 return sum(n / 2) + n * n / 4; 9 }10 else {11 return sum(n - 1) + n; 12 }13 }14 int main() {15 int N;16 cin >> N;17 cout << sum(N) << endl;18 }
网易2017年校招笔试题 最大的奇约数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。