小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数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 + 3 + 7 = 21 小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。 输入描述: 输入一个整数N (1 ≤ N ≤ 1000000000)
输出描述: 输出一个整数，即为f(1) + f(2) + f(3)…….f(N)
输入例子: 7
输出例子: 21
解题思路：易知当n为偶数，f(n)=f(n/2)，n为奇数，f(n)=n。 因为n是10亿，O(n)肯定超时，所以需要求递推公式。 举例： Sum(6)=f(1)+f(2)+f(3)+f(4)+f(5)+f(6) =f(1)+f(1)+f(3)+f(2)+f(5)+f(3) =f(1)+f(3)+f(5)+f(1)+f(2)+f(3) =Sum(3)+1+3+5 所以： sum(n) = sum (n / 2) + 1 + 3 + … + n - 1 （n 为偶数） = sum (n / 2) + (1 + n - 1)*(n/2) /2 = sum (n / 2) +n*n/4 sum(n) =sum(n-1)+n (n位奇数)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; long long Find(int n){ long long sum=0; while(n>0){ if(n%2==0){ sum+=n*n/4; n/=2; }else{ sum+=n; n--; } } return sum; } int main() { int n; scanf("%d",&n); printf("%d\n",n); long long ans=0; printf("%lld\n",Find(n)); return 0; }但是这个代码提交是WRONG的。 我想int 的范围表示10亿是够的，用int表示输入应该是OK的， 但是没注意 sum+=n*n/4 这句,n*n就会直接爆掉。 所以需要把int n改为long long n
