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