首页 > 代码库 > HihoCoder - 1543 SCI表示法

HihoCoder - 1543 SCI表示法

2024-11-14 11:39:39   204人阅读

时间限制: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 }

 

HihoCoder - 1543 SCI表示法


联系
我们