首页 > 其他 > 详细

hihocoder1543 SCI表示法

时间:2017-08-04 21:19:02      阅读:209      评论:0      收藏:0      [点我收藏+]

题意:任何一个数可以表示为连续整数相加,问这些连续整数的最大长度

题解:假设左右是l,r,那么(l+r)*(l-r+1)/2就是这段序列的和,枚举2n的所有因子,找到最大的就可以了

我的做法是预处理前缀和,二分找到答案位置然后暴力 。。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100100
using namespace std;
ll a[maxn];
int main(){
    ll T,n;
    cin>>T;
    for(ll i=1;i<=100010;i++) a[i] = i*(i+1)/2;
    while(T--){
        cin>>n;
        ll l=0,r=100001,ans=-1,mid;
        while(l<=r){
            mid = (l+r)>>1;
            if(a[mid]<=n) ans = mid,l = mid+1;
            else r = mid-1;
        }
        if(a[ans] == n) cout<<ans<<endl;
        else{
            for(ll i=ans;i>=1;i--){
                if((n-a[i])%i == 0){
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

 

hihocoder1543 SCI表示法

原文:http://www.cnblogs.com/Noevon/p/7287052.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!