[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 G: qwb去面试 [找规律]【思维】

Tabris

CSDN思维

发布于：2017年6月3日

次浏览

[原创]2017 年第 0 届浙江工业大学之江学院程序设计竞赛决赛 G: qwb 去面试 [找规律]【思维】

2017-06-03 02:27:50 Tabris_ 阅读数：593

博客爬取于 2020-06-14 22:40:16
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849668

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=6
——————————————————————————————————————————
Problem G: qwb 去面试
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1627 Solved: 260
[Submit][Status][Web Board]
Description
某一天，qwb 去 WCfun 面试，面试官问了他一个问题：把一个正整数 n 拆分成若干个正整数的和，请求出这些数乘积的最大值。
qwb 比较猥琐，借故上厕所偷偷上网求助，聪明的你能帮助他吗？
Input
第一行为一个正整数 T.(T<=100000)
接下来 T 行，每行一个正整数 n(n<=1e9)，意义如题目所述。
Output
每一行输出一个整数，表示乘积的最大值，由于答案可能很大，请将答案对 109+7 取模后输出。
Sample Input
2
2
5
Sample Output
2
6
HINT
2=2
5=2+3
——————————————————————————————————————————

一定是素数的成绩会最大

最开始以为要素因子展开，然后发现，不对，
222<3*3
然后就发现了是尽可能的拆成 3
余 1 就将一个变成 4
余 2 就在乘 2

应该有严谨的证明之类的吧，但是我不会。

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
 
# define abs(x) (((x)>0)?(x):-(x))
 
const int N = 3000+10;
const int MOD  = 1e9+7;
 
/******************************************/
 
LL qmod(LL a,LL b){
    LL res = 1;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return res;
}
 
int main(){
    qmod(3,0);
    int _;
    LL x,y,n;
    scanf("%d",&_);
    while(_--){
        scanf("%lld",&n);
        if(n<5){
            printf("%d\n",n);
            continue;
        }
 
        x=n/3;
        y=n%3;
        if(y==1) x--,y=4;
        if(y==0) y=1;
        printf("%lld\n",qmod(3,x)*y%MOD);
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN