小A买了一个新的存钱罐,他很开心。从他买存钱罐的第 1 天起, 他每天都会往存钱罐里存钱, 第 1 天存 1 元, 第 2 天存 2 元…以此类推, 第 i 天存 i 元, 小A想要知道他最早哪一天能存到 N 元以上, 你能帮他算一算吗。
前3个测试点满足
1≤N≤105
后2个测试点满足
1≤N≤109
所有测试点中 T 满足 1≤T≤105
输入格式:
总共有 T 次询问, Ni表示存钱罐中存到Ni元需要多少天
1 | T |
输出格式:
输出T个数, 表示最早存到 Ni元以上的天数
输入样例:
1 | 2 |
输出样例:
1 | 5 |
对于第一个询问的解释 :
第 1 天存钱罐有 1 元
第 2 天存钱罐有 3 元
第 3 天存钱罐有 6 元
第 4 天存钱罐有 10 元
第 5 天存钱罐有 15 元, 大于 12 元, 因此答案是第 5 天
思路
等差数列an=n,询问该等差数列前n项和,n为几时大于给定的Ni
- 可直接暴力循环计算,会超时
- 利用等差数列求和公式,Sn=(n*(a1+an))/2
代码
1 |
|