ACM - (数论)正整数分解使得乘积最大问题

简介: ACM - (数论)正整数分解使得乘积最大问题

一、问题描述

设 n 是一个正整数。现在要求将 n 分解为若干个自然数之和,使得自然数的成绩最大。输出这个最大的乘积。

要求

(1)要求这些自然数 互不相同。

(2)要求这些自然数 可以相同。(同一个数结果大于等于(1)的结果)

二、问题分析


1、要求这些自然数 互不相同


先来看几个数找找规律

(1)小于等于 4 的情况就不用说了。

(2)从 5 开始写起:5=2+3,6=2+4,7=3+4,8=3+5,9=2+3+4,10=2+3+5,11=2+4+5

 Ps:从 1 开始写没意义,因为相乘还是 1*x==x 还少了相对于原来的 n 还少了 1 呢,更小了,所以从 2 开始才行~


发现规律如下


尽量使得元素是连续的,(一律从 2 开始)。

如果连续加的时候,某个数 k 加的时候正好超出了 n ,则该数 k 不能算入,而是把让 rest =(n - 前面  ( k - 1 ) 项总和),从后往前(因为一开始就使升序,所以也从大到小)均匀分配(+1)到各个元素,直到 rest == 0。


Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int a[100],b[100];
int main()
{
    int rs=0,len=0;
    for(int i=2;rs<=1100;i++)
    {
        a[len++]=i;
        rs+=i;
    }
    int n;
    while(~scanf("%d",&n))
    {
        if(n<=4) // 没办法拆分成不同的数使乘积大于等于 (1*n)
        {
            //...
            continue;
        }
        rs=0;
        int k=0;
        for(int i=0;i<len-1;i++)
        {
            rs+=a[i];
            if(n-rs<a[i+1])
            {
                b[k++]=a[i];
                rs=n-rs;
                int j=k-1;
                while(1)
                {
                    b[j--]+=1;
                    rs--;
                    if(rs<=0) break;
                    if(j==-1) j=k-1;
                }
                break;
            }
            else if(n-rs==a[i+1])
            {
                b[k++]=a[i];
                b[k++]=a[i+1];
                break;
            }
            else
                b[k++]=a[i];
            if(rs<=0) break;
        }
        printf("%d",b[0]);
        for(int i=1;i<k;i++)
            printf(" %d",b[i]);
        puts("");
    }
    return 0;
}



2、要求这些自然数 可以相同


先来看几个数找找规律:4=2+2,5=2+3,6=3+3,7=3+2+2,8=3+3+2,9=3+3+3


发现规律如下


(1)元素不会超过4,因为4=2+2,又可以转化为2的问题,而5=2+3,5<2*3,所以5总能分解成2和3。

(2)尽可能多分解出3,然后分解出2,不要分出1。


考虑任意一个数,除以3之后的结果有以下3种

(1)能被3除断(即整除),那么就分解为3+3+...+3的情况即可。例如:9=3+3+3。

(2)被3除余1,分解为3+3+...+3+2+2或者3+3+...+3+4的情况,例如:10=3+3+2+2

(3)被3除余2,分解为3+3+...+3+2的情况,例如:11=3+3+3+2。


Code(注意:有秒杀公式)


/

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main()
{
    int T; scanf("%d",&T);
    int n;
    while(T-- && ~scanf("%d",&n))
    {
        int rs;
        if(n==0) rs=1; // 根据题目需要
        else if(n<4) rs=n; // 根据题目需要
        else
        {
            int cnt3,cnt2; // 3的个数 2的个数
            if(n%2==1) // 奇数时
            {
                cnt3=(n-3)/6*2+1;
                cnt2=(n-3)%6/2;
            }
            else // 偶数时
            {
                cnt3=n/6;
                cnt2=n%6/2;
            }
            rs=pow(3,cnt3) * pow(2,cnt2);
        }
        printf("%d\n",rs);
    }
    return 0;
}
目录
相关文章
|
算法 测试技术 C语言
【C语言】异或(^)操作符
【C语言】异或(^)操作符
720 0
|
存储 安全 JavaScript
【XSS】XSS漏洞详细指南
【XSS】XSS漏洞详细指南
556 3
|
存储 Java
【编程基础知识】《Java 起航指南:配置 Java 环境变量的秘籍与奥秘》
本文详细介绍了如何配置 Java 环境变量及其重要性,通过具体步骤、代码示例和流程图,帮助初学者轻松掌握 Java 环境变量的设置,为 Java 编程打下坚实基础。关键词:Java、环境变量、配置方法、编程基础。
540 57
|
11月前
|
机器学习/深度学习 人工智能 算法
AI技术在医疗健康领域的应用与挑战####
本文旨在探讨人工智能(AI)技术在医疗健康领域的创新应用及其面临的主要挑战。通过深入分析AI如何助力疾病诊断、治疗方案优化、患者管理及药物研发,本文揭示了AI技术在提升医疗服务质量、效率和可及性方面的巨大潜力。同时,文章也指出了数据隐私、伦理道德、技术局限性等关键问题,并提出了相应的解决策略和未来发展方向。本文为医疗从业者、研究者及政策制定者提供了对AI医疗技术的全面理解,促进了跨学科合作与创新。 ####
|
安全 Java 数据安全/隐私保护
【编程基础知识】《Java 基础之访问权限控制:解锁代码安全与封装的奥秘》
《Java 基础之访问权限控制:解锁代码安全与封装的奥秘》深入探讨了 Java 中的访问权限控制,包括 public、private、protected 和默认权限。通过详细讲解、代码示例和流程图,帮助读者理解不同访问权限的作用和使用场景,提升代码的安全性、可维护性和封装性。
195 3
|
存储 负载均衡 容灾
架构设计|基于 raft-listener 实现实时同步的主备集群
本文介绍如何从数据库内核角度建立一套实时同步的主备集群,确保线上业务的高可用性和可靠性。本系统采用双 AZ 主备容灾机制,并要求数据与 schema 实时同步,同步时延平均在 1 秒内,p99 在 2 秒内。此外,系统支持高效的自动或手动主备切换,并能在切换过程中恢复丢失数据。
332 0
|
SQL 存储 安全
Web安全-CSRF跨站请求伪造
Web安全-CSRF跨站请求伪造
353 4
|
存储 关系型数据库 MySQL
Nomad 系列 -Nomad 挂载存储卷
Nomad 系列 -Nomad 挂载存储卷
|
弹性计算 大数据 测试技术
2024年阿里云服务器租用价格表(CPU/内存/带宽/磁盘收费标准)
2024年阿里云服务器租用价格表更新,云服务器ECS经济型e实例2核2G、3M固定带宽99元一年、ECS u1实例2核4G、5M固定带宽、80G ESSD Entry盘优惠价格199元一年,轻量应用服务器2核2G3M带宽轻量服务器一年61元、2核4G4M带宽轻量服务器一年165元12个月、2核4G服务器30元3个月,幻兽帕鲁4核16G和8核32G服务器配置,云服务器ECS可以选择经济型e实例、通用算力u1实例、ECS计算型c7、通用型g7、c8i、g8i等企业级实例规格。阿里云百科分享阿里云服务器租用费用最新报价
|
JavaScript Java 测试技术
基于SpringBoot+Vue+uniapp的在线学习系统的详细设计和实现(源码+lw+部署文档+讲解等)
基于SpringBoot+Vue+uniapp的在线学习系统的详细设计和实现(源码+lw+部署文档+讲解等)
227 0