牛客网练习赛18 A 【数论/整数划分得到乘积最大/快速乘】

链接：https://www.nowcoder.com/acm/contest/110/A
来源：牛客网

题目描述
这题要你回答T个询问，给你一个正整数S，若有若干个正整数的和为S，则这若干的数的乘积最大是多少?请输出答案除以2000000000000000003(共有17 个零) 的余数。
举例来说，当 S = 5 时，若干个数的和为 5 的情形有以下 7 种(不考虑数字的顺序的话)：

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
5
他们的乘积依序为：
1 * 1 * 1 * 1 * 1 = 1
1 * 1 * 1 * 2 = 2
1 * 1 * 3 = 3
1 * 2 * 2 = 4
1 * 4 = 4
2 * 3 = 6
5 = 5
其中乘积最大的是 2 * 3 = 6。
输入描述:
输入的第一行有一个正整数 T，代表该测试数据含有多少组询问。
接下来有 T 行，每个询问各占 1 行，包含 1 个正整数，代表该询问的 S 值。
输出描述:
对于每个询问，请输出答案除以 2000000000000000003(共有17个零) 的余数。
示例1
输入
10
1
2
3
4
5
6
7
8
9
100
输出
1
2
3
4
6
9
12
18
27
7412080755407364
备注:
1 ≤ T ≤ 100
1 ≤ S ≤ 2000

【[知乎讲解](https://www.zhihu.com/question/30071017/answer/47584748)】 ``` #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug() puts("++++") #define gcd(a,b) __gcd(a,b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define fi first #define se second #define pb push_back #define sqr(x) ((x)*(x)) #define ms(a,b) memset(a,b,sizeof(a)) #define sz size() #define be begin() #define pu push_up #define pd push_down #define cl clear() #define lowbit(x) -x&x #define all 1,n,1 #define mod 2000000000000000003 #define rep(i,n,x) for(int i=(x); i<(n); i++) #define in freopen("in.in","r",stdin) #define out freopen("out.out","w",stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair P; const int INF = 0x3f3f3f3f; const LL LNF = 1e18; const int MAXN = 1e3 + 5; const int maxm = 1e6 + 10; const double PI = acos(-1.0); const double eps = 1e-8; const int dx[] = {-1,1,0,0,1,1,-1,-1}; const int dy[] = {0,0,1,-1,1,-1,1,-1}; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

/*
long long Pow(long long a,long long b)
{
long long res=1;
for(int i=1;i<=b;i++){
res*=a; res %= 2000000000000000003;
}
return res;
}
/
/
LL mul(LL a,LL b)
{
LL ans=0;
while(b)
{
if(b&1) ans=(ans+a)%p;
a=(a+a)%p;
b=b>>1;
}
return ans;
}

LL Pow(LL a,LL b)
{
LL result=1;
LL base=a%p;
while(b)
{
if(b&1) result=mul(result,base)%p;
base=mul(base,base)%p;
b=b>>1;
}
return result;
}
/
int main()
{
long long ans, n;
int t;
cin>>t;
while(t--){
ans = 1;
cin >> n;
while(n>4){
ans=ans3%mod;
n-=3;
cout<<ans<<endl;
}
ans=ans*n%mod;
cout<<ans<<endl;
}
return 0;
}