HihoCoder - 1543 SCI表示法

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。

小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4

+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。

以下 T 行每行一个正整数N。

对于30%的数据,1 ≤ N ≤ 1000

对于80%的数据,1 ≤ N ≤ 100000

对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2
15
8
样例输出
5
1

题目大意:

如题

分析

根据等差数列求和公式,首项为a,功差为1,项数为d,若要满足题意有:

即:

也就是说d一定可以整除2*n

那么从sqrt(2*n)向下开始枚举d

如果d可以整除2*n

那么就可以得到x,如果x为整数,那么d一定是一个可行的连续方案

又因为d从大到小枚举,所以第一个可行解即为答案

代码

 1 include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 #include<cmath>
 5 void deal()
 6 {
 7     int n;
 8     cin>>n;
 9     int sum=0;
10     int ans;
11     for (int i=sqrt(2*n);i>=1;i--)
12     {
13         if (2*n%i==0)
14         {
15             //cout<<i<<" "<<(2*n/i-i+1)<<endl;
16             if ((2*n/i-i+1)%2!=0) continue;
17             ans=i;
18             break;
19         }
20     }
21     cout<<ans<<endl;
22 }
23 int main()
24 {
25     int t;
26     cin>>t;
27     for (int i=1;i<=t;i++)
28     {
29         deal();
30     }
31     return 0;
32 }
时间: 07-30

HihoCoder - 1543 SCI表示法的相关文章

hihocoder1543 SCI表示法

题意:任何一个数可以表示为连续整数相加,问这些连续整数的最大长度 题解:假设左右是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>>

SCI论文从入门到精通

第一部分 经验谈 一.先想先写最后做 做研究之前,必须想清楚:结果能不能发表?发表在哪里? 先把文章大框写好,空出数据,等做完实验填完空就可以发了:正所谓心中有沟壑! 在未搞清“写什么.发哪里.自己研究与同类研究有何出色之处”之前,就不要动手做! 继续去看文献,去想:想不清楚就做还不如不做! 要想这样做,就得先看文献!要知道如何把文章架起来.要知道别人是如何讨论的.要知道自己的数据是不是说明了与别人不同的东东或别人没有做过……这个过程就是阅读文献及思考的过程,这些搞清楚了,写就简单了! 要是先做

SCI科技论文的写作技巧-核心价值

第一次写SCI论文的撰写技巧,本身不是大牛,也许没什么资格谈这个.在此仅是个人的一些思考,对不对,好不好,且当另论. 对于偏向应用的工科生来说,写SCI论文不是一件简单的事情.当然,也不是没可能.全在于如何提取.构思.组织你的论文.论文本身的学术价值当然少不了.但对一个问题,在有的人眼里,就是"这么简单,有什么可写的":而对于另外一些人,却能挖掘出背后的深度.广度.和细度,完成一篇较高价值的论文发表.至于学术价值方面,在次就不赘述.主要谈一下如何来构思SCI的论文,简单概括就是四个字:

扩展欧几里得算法的模板实现

我居然现在还记不住扩欧的板子,我太弱啦! 扩展欧几里得算法解决的是这样的问题: 给定一个不定方程组ax+by=gcd(a,b),求他的一组整数解 先给出实现代码 void exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0;//gcd(a,0)显然等于1*a-0*0=a return a; } int ans=exgcd(b,a%b,x,y); int tem=x; x=y; y-=tem-(a/b)*y; return ans;} 但实

【精品】北京赛车计划冠军定位玩法技巧

車車是一種投資,我們的目標是:細水長流,見好就收,不求日金千金,只求長期穩定!許多人賠本的原因:1. 資金不足,卻大把下注,跟到第4期不出,錢不夠了,心慌了.有人孤注一擲,衝到第5期中了,嚇的半死.有人不敢跟,第5期出號了,氣死, 然後再跟新計劃,沒錢了,郁悶死.這兩種做法都不對,既然是以投資的心態做事,就應該計劃好翻倍的本錢,做到99%的穩賺,狀況不對就要及時止損. 看著連續中,就是不敢跟,最後咬牙跟了,馬上挂了.于是開始哭,我運氣咋這麽差.不買就中,一買就挂.相反,有些人專門等挂,一挂就上,

构建之法——读书笔记(8)

<构建之法>第十&十一章 主要讲述了在软件设计前期的需求分析问题上的方法和实践经验,分为"典型用户和场景"以及"软件设计与实现". 其中第十章大部分内容包含: 用户的分类(典型用户可以包括以下内容: 1. 名字(越自然越好) 2. 年龄(不同年龄和收入的用户有不同的需求) 3. 收入 4. 代表的用户在市场上的比例和重要性(比例大不等同于重要性高,如付费的用户比例较少,但是影响大,所以更重要 5. 使用这个软件的典型场景 6. 使用本软件/服务的

转:梯度下降法(上升法)的几何解释

梯度下降法是机器学习和神经网络学科中我们最早接触的算法之一.但是对于初学者,我们对于这个算法是如何迭代运行的从而达到目的有些迷惑.在这里给出我对这个算法的几何理解,有不对的地方请批评指正! 梯度下降法定义 (维基百科)梯度下降法,基于这样的观察:如果实值函数  在点  处可微且有定义,那么函数 在  点沿着梯度相反的方向  下降最快. 因而,如果                         对于  为一个够小数值时成立,那么 . 考虑到这一点,我们可以从函数  的局部极小值的初始估计  出发

1024. 科学计数法 (20)

科学计数法是科学家用来表示很大或很小的数字的一种方便的方法,其满足正则表达式[+-][1-9]"."[0-9]+E[+-][0-9]+,即数字的整数部分只有1位,小数部分至少有1位,该数字及其指数部分的正负号即使对正数也必定明确给出. 现以科学计数法的格式给出实数A,请编写程序按普通数字表示法输出A,并保证所有有效位都被保留. 输入格式: 每个输入包含1个测试用例,即一个以科学计数法表示的实数A.该数字的存储长度不超过9999字节,且其指数的绝对值不超过9999. 输出格式: 对每个测

五大常用算法之四:回溯法

(转自:http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html) 1.概念 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径. 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”. 许