POJ 2739 Sum of Consecutive Prime Numbers
连续素数和:将一个整数分解为连续的素数之和,有多少种分法?
3.2常用技巧精选(一)
尺取法
简单,一次就AC了。先艾氏筛法做一份素数表,然后在素数表上爬行一遍就行了。最近好多事,通宵吧,第二天吃不消,不通宵吧,事情多得睡不着……
#include <iostream> #include <vector> using namespace std; #define MAX_N 10000 + 16 // 先生成MAX_PRIME内的素数表 #define MAX_PRIME MAX_N vector<int> primes; vector<bool> is_prime; void init_primes() { is_prime = vector<bool>(MAX_PRIME + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= MAX_PRIME; ++i) { if (is_prime[i]) { primes.push_back(i); for (int j = i * 2; j <= MAX_PRIME; j += i) { is_prime[j] = false; } } } } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif init_primes(); const int size = primes.size(); int n; while (cin >> n && n) { int l = 0, r = 0, sum = 0, result = 0; for (;;) { while (sum < n && r < size) { sum += primes[r++]; } if (sum < n) { break; } else if (sum == n) { ++result; } sum -= primes[l++]; } cout << result << endl; } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
又看到了神奇的0毫秒:
12877923 | hankcs | 2739 | Accepted | 260K | 0MS | C++ | 1226B | 2014-05-15 00:05:01 |