网易那个奇约数？一起交流下？

#include <iostream> using namespace std; int main(){ long n; int i,j; int sum = 0; while(cin>>n){ i = 1; while(n > 1){ if(n%2 == 1){ sum += (n+1)*(n+1)/4; n = (n-1)/2; } else{ i = n; while(i%2 == 0) i /= 2; sum += i; } } sum++; cout<<sum<<endl; } return 0; }

递归，求奇数列的和，用公式，偶数列除2又是连续数列，然后继续用公式求这个数列的奇数列，递归就好了

应该是等差数列吧， 举例： 对于1,2,3,4,5,6,7,8,9;对应的节约数为1,1,3,1,5,3,7,1,9; 可以发现： 1+3+5+7+9     n=9 1+3                 n=4    (9/2) 1                     n=2    (4/2) 1                     n=1     (2/2)

谷歌有这道题的解析，递归调用

http://www.nowcoder.com/discuss/9620?type=0&order=3&pos=28&page=1 这里有解析 哎 我也是一直超时

我总结了个公式，logn可以，但是数据溢出，用int_t也溢出，用手机回复的，暂时不能打公式，奇怪，网友用的long long 就AC了

def MaxPrime(N): while(N % 2 == 0): N = N / 2 return N def sumMaxPrime(N): sum = 0 for x in xrange(1, N + 1): if x % 2 != 0: sum = sum + x else: sum = sum + MaxPrime(x) print sum if __name__ == '__main__': sumMaxPrime(400)

s(n) = 小于等于n的所有奇数之和 + s(n / 2) 时间复杂度log(n)

package test.wangyi; import java.util.Scanner; /**  *   * Description: netease coding test 2.  */ public class Main2 { public static void solve() { Scanner reader = new Scanner(System.in); while(reader.hasNext()) { long N = Integer.parseInt(reader.nextLine()); long count = 0; count = deal(N); System.out.println(count); } reader.close(); } public static long deal(long N) { if(N == 1) { return 1L; } if(N % 2 != 0) { long part = (1 + N) * (N + 1) / 4; return part + deal((N - 1) / 2); } else { long part = N * N / 4; return part + deal(N / 2); } }    public static void main(String[] args) {  Main2.solve();   } }

#include "iostream" using namespace std; typedef long long LL; int main() { LL N; LL Ans = 0; while (cin >> N) { Ans = 0; for (LL i = N; i > 0; i = i / 2) Ans += ((i + 1) / 2) * ((i + 1) / 2); cout << Ans << endl; } return 0; } 我是这么写的，up可以参考一下。注意公式里面要套扩考，优先级错了，结果会出问题