首页 > 试题广场 >

最大的奇约数

[编程题]最大的奇约数
  • 热度指数:30922 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数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)
示例1

输入

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;
		}
	}
	
}


发表于 2016-09-26 22:06:47 回复(4)
#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;
}
*/

发表于 2017-09-02 17:30:22 回复(2)
```
# 来个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))

```

发表于 2018-08-08 21:34:39 回复(1)
由于输入的n太大,所以保存前面结果的方法不适用于本题

奇数的最大奇约数是它本身,因此先将所有奇数加起来。
偶数的最大奇约数和对当前值除2之后的最大奇约数的值是相同的。所以处理偶数时将所有偶数先除以2,然后重复之前的处理

#include<iostream>
using namespace std;

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;
}
发表于 2017-09-01 20:08:29 回复(0)
#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;
}
1.判断n是否为奇数,如果为奇数,求所有奇数的和
2.如果为偶数,求最后一个偶数的最大质约数,在求前n-1的奇数和
3.在n减半,依次循环求和
最后时间复杂度为lg(n)到lg(n)*lg(n)之间
编辑于 2016-09-13 12:12:35 回复(2)
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)

编辑于 2018-09-12 11:23:49 回复(0)
#include <iostream>
using namespace std;
int main(){
	long long int n,sum=0;
	cin>>n;
	while(n){
		if(n%2==1){
			sum+=n;
			n--;
		}else{
			sum+=n*n/4;
			n/=2;
		}
	}
	cout<<sum<<endl;
	return 0;
}

发表于 2017-08-25 18:18:18 回复(1)
def getSum(n):
    if(n==1):
        return 1;
    return n*n/4+getSum(n/2) if n%2==0 else n+getSum(n-1);
def main():
    while(True):
        try:
            n=int(raw_input().strip());
            print getSum(n);
        except:
            break;
main();
      

编辑于 2016-09-13 09:59:46 回复(1)
整体思路是这样:奇数的最大奇约数就是它本身,偶数的最大奇约数就是不断除以2,直到得到第一个奇数。但是如果将奇数项用高斯求和公式求和,然后偶数采用这种方法进行遍历是会超时的,因此我们只能寻找其他方式,尽可能地多用求和公式,将O(n)尽可能转为O(1)。
假如n=10,则序列为1,2,3,4,5,6,7,8,9,10,奇数项直接求和,剩下一半是偶数:2,4,6,8,10,都除以2得到:1,2,3,4,5。
假如n=9,则序列为1,2,3,4,5,6,7,8,9,奇数项直接求和,剩下4(4=9/2)个偶数:2,4,6,8,都除以2得:1,2,3,4。
发现规律:f(n)=f(n/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;
    }
}

发表于 2021-04-05 12:06:02 回复(0)

奇数的最大约数就是本身。sum(n) 就是求 i为偶数的和 加上 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) = sum (n - 1) + n (n为奇数)
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))
编辑于 2019-08-02 21:20:51 回复(0)
#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;
}
发表于 2018-09-28 11:57:59 回复(1)
#include <iostream>

using namespace std;

typedef long long ll;

int main()
{     ll N, result = 0;     while(cin>>N)     {         result = 0;         for(ll i=N;i>0;i/=2)             result += ((i+1)/2) * ((i+1)/2);         cout<<result<<endl;     }     return 0;
}

发表于 2018-01-27 01:22:17 回复(0)
#include<stdio.h>
int main(){
    long long N=1,i;
    while(scanf("%lld",&N)!=EOF){
        long long res=0;
        for(;N;N/=2){
            long long a1=1,an=(N%2?N:N-1);
            res+=(a1+an)*((an-a1)/2+1)/2;
        }
        printf("%lld\n",res);
    }
}

发表于 2017-10-19 11:10:43 回复(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;
}
编辑于 2017-08-12 14:44:01 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N,sum=0;
    scanf("%lld",&N);
    for(long long i=N;i>0;i/=2){
        sum+=((i+1)/2)*((i+1)/2);
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2017-08-10 08:46:18 回复(1)
既然是数论题,那这里给出一个纯数学解法,复杂度O(logn):

#include <iostream>
#include <cmath>
using namespace std;
long long sqr(long long x){return x*x;}
int main()
{
    long long ans=0,k,n;
    cin >> n;
    for (k=2;k<=2*n;k*=2)
        ans+=sqr(round(n*1.0/k));
    cout << ans;
}

编辑于 2017-07-07 17:10:08 回复(0)

Java

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);

    }

}

递归做法,至于思路,上面已经很清楚了。

发表于 2017-03-24 19:17:14 回复(0)
//递归
long long ff(long long n)
{
	if (n == 1) return 1;
	if (n & 1 == 1)
		return (n + 1)*(n + 1) / 4 + ff((n - 1) / 2);
	else
		return n*n / 4 + ff(n / 2);
}

编辑于 2017-03-09 23:35:50 回复(0)
#!/usr/bin/env python

def f(x):
    if x % 2 != 0:
       return x
    else:
        return f(x/2)

if __name__ == '__main__':
     NUM = int(raw_input("Please input the number:>"))
     SUM = 0
      for i in range(1, NUM + 1):
            SUM = SUM + f(i)

     print SUM
                
发表于 2016-11-01 14:23:13 回复(1)
#include <iostream>
using namespace std;
long func(int n){

    if( n == 1 ){
        return 1;
    }
    long temp = ((n+1)/2);
    return temp*temp+func(n/2);
}
int main(){

    int n;
    cin>>n;
    cout<<func(n)<<endl;
}
发表于 2016-09-24 13:15:21 回复(0)