首页 > 试题广场 >

最大的奇约数

[编程题]最大的奇约数
  • 热度指数：31983 时间限制：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
算法知识视频讲解
添加回答
卷积神经网络哦头像 卷积神经网络哦 
```
# 来个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)
C/C++
卡玛酱头像 卡玛酱 
#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)
Coast2头像 Coast2 
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)
2019眷顾我头像 2019眷顾我 
#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)
C/C++
nbgao头像 nbgao 
#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)
C/C++
JonTargaryen头像 JonTargaryen 
#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)
hades496头像 hades496
既然是数论题，那这里给出一个纯数学解法，复杂度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)
pore头像 pore 
//递归
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)
Python
17浪头像 17浪 
#!/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)
辉88头像 辉88
#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)
selfboot头像 selfboot 
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N;
    while (cin >> N){
        long long sum = 0;
        /*
         * n 为偶数(奇数时情况区别不大)
         * f(1) + f(2) + ... + f(N) = f(2) + f(4) + ... + f(N) + f(1) + f(3) + ... + f(N-1)
         * f(1) + f(3) + ... + f(N-1) = 1 + 3 + ... + N-1 = (N)*(N)/4;
         * f(2) + f(4) + ... + f(N) = f(1) + f(2) + ... + f(N/2);       !!! Important here.
         */
        while (N){
            if((N&0x1)==1){
                sum += (long long)(N+1)*(N+1)/4;    // 防止溢出
                N = (N-1)/2;
            }
            else{
                sum += (long long)(N)*(N)/4;
                N = N/2;
            }
        }
        cout << sum << endl;
    }
    return 0;
}


发表于 2016-09-17 10:29:30 回复(0)
anas头像 anas 
/*思路是：如果n是偶数，采用折半的方式，如果为奇数，首先将最后一个奇数加到结果中，然后再求前面n-1个偶数的结果*/
#include<iostream>
using namespace std;
int main(){
    long n;
    while(cin>>n){
        long long sum=0;
        while(n){
            if(n%2==1){//如果是奇数个元素，将最后一个奇数加到结果中
                sum+=n;
                --n;//然后求前面n-1个偶数的结果
            }
            else{
                sum+=(1+n-1)/2*n/2;//如果是偶数个元素，采用折半的方式，后面n个元素一次为1，3，5，7，。。。n-1
                n/=2;
            }               
        }
        cout<<sum<<endl;
    }
    return 0;
}

发表于 2016-09-14 08:27:11 回复(1)
pngfi头像 pngfi 
import java.util.Scanner;


public class Main{
	
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		long num=s.nextInt();
		long sum=0;
		for(long i=num;i>0;i=i/2){
			long temp=(i+1)/2;
			sum+=temp*temp;
		}
		System.out.println(sum);
	}
}


总体思路：
因为奇数的最大奇数约数就是自己啊，对于偶数我们只能一直除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)
因此两种情况可以用一个等式来总结

发表于 2016-09-18 22:40:32 回复(39)
C/C++
武汉孙一峰头像 武汉孙一峰 
//找规律，你会发现基数都是直接取，偶数/2，得到的基础直接取，偶数继续/2，每次循环，可以把规模缩小1/2。
//要注意的是((i + 1) / 2) * ((i + 1) / 2)运算时候，括号的优先级。

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

编辑于 2016-09-13 13:47:35 回复(15)
Alex-大伟头像 Alex-大伟 
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)
rs勿忘初心头像 rs勿忘初心 
#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)
C/C++
GODZ头像 GODZ 
#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)
C/C++
一往无前666头像 一往无前666
由于输入的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)
提交观点

问题信息

模拟 穷举 数学
来自：网易2017秋招编程题集合
难度：
103条回答 21710浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大的奇约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号