首页 > 代码库 > HDU5976 Detachment
HDU5976 Detachment
1 /* 2 HDU5976 Detachment 3 http://acm.hdu.edu.cn/showproblem.php?pid=5976 4 数论 等差数列 5 * 6 * 7 */ 8 #include <cstdio> 9 #include <algorithm> 10 #include <vector> 11 using namespace std; 12 const int mod=1000000007; 13 const int Nmax=50001; 14 vector<long long> v; 15 long long f[Nmax]; 16 long long g[Nmax]; 17 long long qpow(long long base,int n) 18 { 19 long long ans=1LL; 20 base=base%mod; 21 while(n>0) 22 { 23 if(n&1) 24 ans=ans*base%mod; 25 base=(base*base)%mod; 26 n>>=1; 27 } 28 while(ans<0) 29 ans+=mod; 30 return ans; 31 } 32 33 int main() 34 { 35 //freopen("3.in","r",stdin); 36 int t; 37 scanf("%d",&t); 38 long long x; 39 f[1]=1LL; 40 41 f[0]=0LL; 42 f[2]=2LL; 43 g[1]=1LL; 44 g[2]=2LL; 45 v.push_back(f[1]); 46 v.push_back(f[2]); 47 for(int i=3;i<Nmax;i++) 48 { 49 g[i]=1LL*i*g[i-1]%mod; 50 f[i]=1LL*i+f[i-1]; 51 v.push_back(f[i]); 52 } 53 //printf("%lld\n",f[Nmax-1]); 54 while(t--) 55 { 56 long long ans=1LL; 57 scanf("%lld",&x); 58 int j=1; 59 int k=1; 60 for(int i=1;i<Nmax;i++) 61 { 62 if(x>=f[i] && x<f[i+1]) 63 { 64 j=i; 65 break; 66 } 67 } 68 //printf("bj:%d\n",j); 69 j=lower_bound(v.begin(),v.end(),x)-v.begin(); 70 while(!(x>=f[j]&& x<f[j+1])) 71 j++; 72 //printf("j:%d\n",j); 73 long long remain=x-f[j]; 74 if(remain) 75 { 76 if(remain==j) 77 k=2; 78 else 79 k=j+1-remain; 80 //printf("j:%d k:%d\n",j,k); 81 ans=g[j]; 82 ans=ans*qpow(1LL*k, mod-2 )%mod; 83 ans=ans*(k+remain)%mod; 84 } 85 else 86 { 87 ans=g[j]; 88 } 89 while(ans<0) 90 ans+=mod; 91 printf("%lld\n",ans); 92 } 93 return 0; 94 }
HDU5976 Detachment
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。