网易笔试，求最大奇约数和，O(n)复杂度超时

long long findSum(int N) { if (N == 1) return 1; long long k = (N + 1) / 2; return k*k + findSum(N / 2); } 神公式

int main() { int n; cin >> n; long long sum = 0; int t; for (int i = 1; i <= n; i += 2) { t = i; while (t <= n) { t *= 2; sum += i;} } cout << sum; }

考试后，和学弟们讨论得出了答案，logn的，也去网易的笔试题真题哪里测试了下，通过了，虽然笔试中没有做出来，不过后来没有看别人的现成的答案，而是我们集思广益想出来的，还是蛮开心的，这也是笔试的收获吧

怎么说呢。我觉得其实有规律的。 每4个看成一组。 不过最近一直没去解。。当时考试考到最后几分钟才反映过来。

位运算可以 res = n / (n & -n)  得到最大奇数

#include <iostream> using namespace std; int main() {     long n;     cin>>n;     long long res=0;     long t=2;//用t表示2^k     int count=0;     while(count<n/2)     {         for(long i=1;t*i<=n;i=i+2)//找到2^k*i<=n的所有i         {             res=res+i;             count++;           }         t=t*2;     }     if(n%2==0) //当n为奇数时，序列中的奇数和     {         res=res+n*n/4;                 }     else//当n为偶数时，序列中的奇数和     {         res=res+(n+1)*(n+1)/4;             }     cout<<res<<endl;     return 0; }

用移位操作做除2操作就可以不超时

推公式推了半天, 只能O(1)的解决一半, 剩下的一半推死推不出来.  比如对于100的话能直接算出1-64的和 , 最后没办法只好遍历了. 没想到过了.

开始用python一直超时，换C++才AC了

unsigned long long cal(unsigned long long n){ unsigned long long sum = 0; do { if (n % 2 == 0) { sum += (long long)(n/2)*(n / 2); n = n / 2; } else { sum += n; n = n - 1; } } while (n != 1); return sum + 1; }

超时 ，好伤心。

哎，O(logN)

一直除以2超时，改成移位运算超时，我真不知道怎么做了，与网易无缘了，😭

都100亿了，O(N)肯定超时啊。O(N)在1s内也就解1亿左右的数据了，常数还不能太大

C++超时……

最大奇约数，奇数就是本身，偶数/2直到奇数为止，但还是不行，始终要循环

最后想起来的，妈的交卷了，坑爹啊

每个奇数*2*2*2。。。

在交卷的一瞬间，我知道我超时的原因了，一直除以二就可以解决问题，再次GG

看了讨论区logn的答案，真是觉得生无可恋了