时间限制: 1 Sec 内存限制: 128 MB 提交: 197 解决: 58
题目描述 Given a positive integer N, split it into K non-negative integers. i.e. N = x1+x2+..+xk. Define p as the product of all integers in the set. i.e. p=x1*x2…*xk.
What’s the maximum possible value of p ? Since p may be very large, just print p00000007.
输入 Each line contains two integers N and K separated by space.1≤ N≤ 1000000000
, 1≤ K≤100。 Process to end of file.
输出 For each case, you should output maximum product mod 1000000007.
样例输入 3 3 4 3 样例输出 1 2
分析：余数与商的关系
#include<cstdio> typedef long long LL; const int mod=1e9+7; LL pow_mod(LL a,LL b,LL mod) { LL ans=1; a%=mod; while(b) { if(b&1) ans=(ans*a)%mod; b>>=1; a=(a*a)%mod; } return ans; } int main() { LL n,k; while(~scanf("%lld%lld",&n,&k)) { LL m=n%k,tmp=n/k; LL t=tmp,ans=t,num=1; if(m) { t=1+tmp; num=m; ans=pow_mod(t,m,mod)%mod; } LL r=k-num; for(int i=0; i<r; i++) ans=ans*((n-num*t)/r)%mod; printf("%lld\n",ans); } return 0; }