[原创]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;
}