小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数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
package com.suda.alex; import java.util.Scanner; public class Test6 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); System.out.println(sumOfMaxOdd(n)); } } /* * 奇数的最大约数就是本身。问题就是求所有f(i), i为偶数的和 因为要求的是最大奇约数,所以f(2k) = f(k),所以f(2) + f(4) * + ... + f(2k) = f(1) + f(2) + ... + f(k); * * sum(n) = sum (n / 2) + 1 + 3 + ... + n - 1 = sum (n/2) + n*n/4(n 为偶数) * * = sum (n - 1) + n (n为奇数) * * */ public static long sumOfMaxOdd(long n) { if (n == 1) { return 1; } if (n % 2 == 0) { return sumOfMaxOdd(n / 2) + n * n / 4; } else { return sumOfMaxOdd(n - 1) + n; } } }
#include<iostream> using namespace std; /* 总体思路: 因为奇数的最大奇数约数就是自己啊,对于偶数我们只能一直除2直到得到一个奇数即为最大奇数约数 比如1 2 3 4 5 6 7 8 9 10 即n=10 ,此时奇数有1 3 5 7 9 我们把这几个奇数相加然后n/2 得到第二轮序列序列 1 2 3 4 5 分别对应上次的2 4 6 8 10 五个偶数,这是我们再加1 3 5 依次类推 细节问题: 当n为偶数,就有n/2个奇数,根据等差数列求和公式 即((首项+末项)*项数)/2,我们知道n/2个奇数和为((1+n-1)*n/2)/2, 即为(n/2) * (n/2),此时n为偶数,因此 (n/2) * (n/2) = ((n+1)/2) * ((n+1)/2) 当n为奇数,有(n+1)/2个奇数,此时奇数和为((n+1)/2) * ((n+1)/2) 因此两种情况可以用一个等式来总结 */ //找规律:假设n=16 //while第一次:sum+=1+3+5+7+9+11+13+15(所有奇数的最大奇约数为本身),同时n减半(/2)为8 //while第二次:sum+=1+3+5+7(对应的是16,14,12,10的最大奇公约数),同时n减半为4 //while第三次:sum+=1+3(对应的是8,6的最大奇公约数),同时n减半为2 //while第四次:sum+=1(对应的是4的最大奇公约数),同时n减半为1 //while第五次:sum+=1(对应的是2的最大奇公约数),同时n减半为0 int main() { int n; long long sum = 0; cin >> n; while (n) { for (int i = 1; i <= n; i += 2) sum += i; n /= 2; } cout << sum; system("pause"); return 0; } /*常规方法超时 #include<iostream> using namespace std; int maxOddDivNum(int num) { for (int i = num; i >= 1; i--) { if (num % i == 0 && i % 2 != 0) return i; } return 1; } int main() { int n; while (cin >> n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += maxOddDivNum(i); } cout << sum << endl; } return 0; } */
```
# 来个python的递归实现,数据很大要用Decimal处理大数字
# 前提:奇数的最大奇约束就是他自己,偶数的最大奇约束就是一直除以2直到除成奇数
# 分奇数偶数,当n为偶数时,n以下的奇数全部加起来,即n^2/4, 剩下的偶数都除以二就变成
# 了1,2,3,...,n/2这就可以递归了。当n为奇数是也是类似的
from decimal import *
n = int(input())
def digui(n):
if n == 1:
return 1
if n % 2 == 0:
return Decimal(n**2)/Decimal(4) + digui(Decimal(n/2))
else:
return Decimal((n+1)**2)/Decimal(4) + digui(Decimal((n-1)/2))
print(digui(n))
```
#include <iostream> using namespace std; int main() { long long n; while(cin>>n){ long long sum = 0; while(n > 0) { if (n%2 == 0) { long long temp = n; while(temp!=1){ temp /= 2; if(temp%2 == 1) break; } sum += temp; n = n-1; } sum += (n+1)*(n+1)/4; n /= 2; } cout<<sum<<endl; } return 0; }
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); long n = in.nextLong(); System.out.println(s(n)); } public static long s(long n){ if(n==1){ return 1; } if(n%2==0){ return (n/2)*(n/2) + s(n/2); }else{ return ((n+1)/2)*((n+1)/2) + s((n-1)/2); } } } 这题巨坑,提交了四五次才通过。 1.首先算法复杂度必须要尽可能的小,这里不能考虑枚举,而是应该以奇数偶数分治 (考虑两个点:n为奇数和偶数时;12345678910分治成13579的和加上246810即12345的和 ),最后采取递归的算法才可以在提交时跑的出结果。 2.由于测试的数字有10亿级着这么大所以得用long长整型存储。 3.Math.pow默认返回值是double型,所以强制转换成long型会丢失部分精度,在如此大级别 的数的运算中最后的值就会有差别(所以通过不了)因此这里得用a*a代替Math.pow(a,2)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(br.readLine()); System.out.println(helper(n)); } private static long helper(long n) { if(n == 1) return 1; if(n % 2 == 0) return helper(n / 2) + n*n / 4; else return helper(n / 2) + (n + 1)*(n + 1) / 4; } }
奇数的最大约数就是本身。sum(n) 就是求 i为偶数的和 加上 i 为奇数的和
对于i为偶数的和 f(2k) = f(k),解释如下:
N = int(input()) # TLE: # res = 0 # for i in range(1,N+1): # while i&1 == 0: # i = i>>1 # res += i # print(res) def sumDivisor(n): if n == 1: return 1 if n&1: return n + sumDivisor(n-1) else: return sumDivisor(n>>1) + n**2//4 print(sumDivisor(N))
#include <iostream>
using namespace std;
long long sum(long long N){
if(N==1)return 1;
long long res=0;
if(N%2==0){
res+=N*N/4;
res+=sum(N/2);
}else{
res+=(N+1)*(N+1)/4;
res+=sum((N-1)/2);
}
return res;
}
int main(){
long long N;
while(cin>>N){
cout<<sum(N)<<endl;
}
return 0;
}
#include <stdio.h> long bigOddSum(long num, long sum) { if (num == 0) { return 0; } if (num % 2) { sum += (num / 2 + 1) * (num / 2 + 1); sum += bigOddSum((num-1)/2, 0); } else { sum += (num / 2) * (num / 2); sum += bigOddSum((num)/2, 0); } return sum; } int main() { long num; long sum = 0; scanf("%ld", &num); sum = bigOddSum(num, 0); printf("%ld\n", sum); return 0; }
import java.util.Scanner;
public class FunctionPlus {
private static long plus;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(getPlus(sc.nextInt()));
sc.close();
}
private static long getPlus(int n) {
if (n == 1)
return plus + n;
for (int i = 1; i <= n; i += 2) {
plus += i;
}
return getPlus(n / 2);
}
}
递归做法,至于思路,上面已经很清楚了。