首页 > 代码库 > 2016 ICPC大连站---F题 Detachment
2016 ICPC大连站---F题 Detachment
题意:输入一个x,将x拆分成一些小的数(这些数不能相同,即x=a1+a2+...... ai!=aj when i!=j),然后这些数相乘得到一个成积(s=a1*a2*......),求最大的乘积s;
思路:考虑最简单的做法便是贪心,很明显将一个数分的越小,这个乘积越大,那么对于给的x 先找2+3+4+....+n<=x 找到最大的n 如果和小于x ,那么将n右移一个数(n->n+1) 如果和还小于x继续将n-1右移......知道和x相等时,输出s 这样做时间复杂度很高,那么得优化。 由上面的过程分析发现,2+3+...+n<=x &&2+3+...+n+(n+1)>x
那么x-(2+3+...+n)<=n 那么最终x分成的数结果只有三种情况:x=2+3+...+(k-1)+(k+1)+...+n+(n+1) x=3+4+...+n+(n+1) x=3+4+...+(n-1)+n+(n+2)
其实第一种和第二种情况相同。 分析过程如上,详细计算过程如下:2+3+...+n<=x 所以n*(n+1)<=2*x+2 n<=sqrt(2*n+2)
代码如下:
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <bitset>using namespace std;typedef long long LL;const LL mod=1e9+7;const LL maxn=1e5+5;LL A[maxn],s[maxn];LL Inv[maxn];void getINV()///逆元;{ Inv[1]=1; for(LL i=2; i<maxn; i++) Inv[i] = (mod-mod/i)*Inv[mod%i]%mod;}void init(){ s[1]=0; for(LL i=2;i<maxn;i++) s[i]=s[i-1]+i; A[0]=1; for(LL i=1;i<maxn;i++) A[i]=A[i-1]*i%mod; getINV();}int main(){ init(); int T; cin>>T; while(T--) { int pos; LL x,sum; scanf("%lld",&x); LL n=(LL)(sqrt(2*x+2)); for(int i=n;i>=1;i--) if(s[i]<=x){ pos=i; break; } if(x==1) { puts("1"); continue; } if(s[pos]==x) { printf("%lld\n",A[pos]); continue; } if(s[pos]+pos-1>=x){ LL tot=s[pos]+pos-1-x; sum=(A[pos+1]*Inv[tot+2])%mod; } else{ LL tot=s[pos+1]-2+pos-1-x; sum=((A[pos+2]*Inv[2])%mod)*Inv[tot+3]%mod; } printf("%lld\n",sum); } return 0;}
2016 ICPC大连站---F题 Detachment
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。