POJ 2140 解题报告

本文主要是介绍POJ 2140 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题用的是求和公式：假设首项是a，一共k项，那么有(a + a + k - 1) * k / 2 = N。即(2a + k - 1) * k = 2N。我们有2a + k - 1和k都是2N的因数，验证能否整除即可。一个优化是2a + k - 1 >= 2 * 1 + k - 1 = k + 1 > k。所以k只需要取到sqrt(2N)即可。

thestoryofsnow

2140

Accepted

160K

32MS

C++

632B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj2140 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;int main()
{int N;	scanf("%d", &N);const int N2 = N * 2;const int UPPER = sqrt((double)N2);int cnt = 0;for (int k = 1; k <= UPPER; ++k){if (N2 % k == 0 && (N2 / k + 1 - k) % 2 == 0){cnt++;}}printf("%d\n", cnt);return 0;  
}

这篇关于POJ 2140 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---