1.Get all primes in [2,10000];
2.Reset the counter to 0. Then, start from 2 and calculate the sums, namely, 2, 2+3, 2+3+5, ..., until the sum is great than 10000; for those who are less than that, increase the counter of that sum, correspondingly, 2,5,10,......
3.For each input between 2 and 10000, output the precalculated sum.
Source code as followed:
#include <cmath>
using namespace std;
const int MAXN = 10000;
bool f[MAXN+10];
int np;
int p[MAXN+10];
int sum[MAXN+10];
void findPrime() {
memset(f, 1, sizeof(f));
f[0] = 0; f[1] = 0;//doesn't matter anyway
int tmp = abs(sqrt(MAXN*1.0));
for (int i = 2; i <= tmp; i++) {
if (f[i]) {
for (int j = i+i; j <= MAXN; j+=i)
f[j] = 0; //false
}
}
int ctr = 0;
for (int i = 2; i <= MAXN; i++)
if (f[i]) {
p[ctr++] = i;
}
np = ctr;
}
void geneSum() {
memset(sum, 0, sizeof(sum));
for (int i = 0; i < np; i++) {
int tsum = 0;
for (int j = i; j < np; j++) {
tsum += p[j];
if (tsum > MAXN) break;
sum[tsum]++;
}
}
}
void initi() {
findPrime();
geneSum();
}
int main() {
initi();
int n;
while (1) {
scanf("%d", &n);
if (n == 0) break;
printf("%d\n", sum[n]);
}
return 0;
}
空域濾波技術根據功能主要分為平滑濾波與銳化濾波，平滑濾波能減弱或消除圖像中的高頻率分量而不影響低頻分量。因為高頻分量對應圖像中的區域邊緣等灰度值 具有較大變化的部分，平滑濾波可將這些分量濾去減少局部灰度起伏，是圖像變得比較平滑。實際應用中，平滑濾波還可用于消除噪聲，或在提取較大目標前去除太 小的細節或將目標的小間斷連接起來。銳化濾波正好相反，實際應用中銳化濾波常用于增強被模糊的細節或目標的邊緣。
空域濾波是在圖像空間通過鄰域操作完成的，實現的方式基本都是利用模板（窗）進行卷積來進行，實現的基本步驟為：
1、將模板中心與圖中某個像素位置重合；
2、將模板的各個系數與模板下各對應像素的灰度值相乘；
3、將所有乘積相加，再除以模板的系數個數；
4、將上述運算結果賦給圖中對應模板中心位置的像素。
常見的空域濾波器：
1、鄰域平均：將一個像素鄰域平均值作為濾波結果，此時濾波器模板的所有系數都取為1。
2、加權平均：對同一尺寸的模板，可對不同位置的系數采用不同的數值。實際應用中，常取模板周邊最小的系數為1，而取內部的系數成比例增加，中心系數最 大。
加權平均模板示例：
1 2 1
2 4 2
1 2 1
3、高斯分布：借助楊輝三角對高斯函數進行近似。
高斯模板系數：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
4、中值濾波：中值濾波是一種非線性濾波方式，可用如下步驟完成。
（1）將模板在圖中漫游，并將模板中心與圖中某個像素位置重合；
（2）讀取模板下各對應像素的灰度值；
（3）將這些灰度值從小到大進行排序；
（4）找出中間值并賦給對應模板中心位置的像素。
一般情況下中值濾波的效果要比鄰域平均處理的低通濾波效果好，主要特點是濾波后圖像中的輪廓比較清晰。
5、最頻值濾波：通過直方圖統計中心像素點的灰度分布情況，將出現次數最多的灰度值（即直方圖波峰位置）賦給中心位置的像素。如果直方圖是對稱的且僅有一
個峰，那么均值、中值和最頻值相同。如果直方圖僅有一個波峰但不對稱，那么最頻值對應波峰，而中值總比均值更接近最頻值。
6、銳化濾波：圖像銳化一般是通過微分運算來實現的，圖像處理中最常用的微分方法是利用梯度（基于一階微分）。在離散空間，微分用差分實現，常用的差分模板如下：
-1 1
1 1 1
-1 1
用F[i]表示得到i面值所需要的最少郵票個數，Value[j](j=1..Stamps)表示每個郵票的面值，可得以下轉移方程：
F[i]=Min ( F[i-Value[j]] + 1 ) (i-Value[j]>=0 j=1..Stamps)
初始狀態：F[0]=0;F[i]=INFINITE;
相當于一個映射，而不能片面的理解成移位的意思。前面就是因為這個wa的……
注意讀題，不要被水題水了。
}
Poj 1597 – Uniform Generator
題目的意思就是一個生成隨機數的函數，
Seed[x+1] = （ seed[x] + STEP ） % MOD
其中seed就是我們生成出來的隨機數，至于seed[0]是哪個數并不重要，后面會證明。STEP就是我們每次往前一個所加的值，再module上MOD得到下一個隨機數。
判斷這個隨機生成函數的好壞的依據是如果能夠產生0~MOD-1內的所有數，就是一個好的，否則壞。
我們知道了同余的特性，便可以假設在k步之后，生成的seed[k] = seed[0]，所以由此有
Seed[k] = （ seed[0] + STEP*k ） % MOD
那么，
STEP * k = MOD
而我們如果要生產MOD個數，必須使k≥MOD，而且k不可能大于MOD，因為這個條件下生成的數又開始重復，所以k=MOD；在前面的條件下，如果STEP和MOD有大于1的公約數例如d，那么會有STEP*(k/d) = MOD，這就是一個循環了，只會產生k/d<MOD個隨機數。
結論：iff gcd(STEP, MOD) == 1, good choice.
Poj 3370 Halloween treats
這道題在集訓手冊上標志是“抽屜原理”，老實說，在看到這道題的具體解法之前，我還不知道為什么是抽屜原理，這明明是判斷一些數的同余嘛，后來才發現鴿籠原理的巧妙之處。
4 5
1 2 3 7 5
例如對于第一組數據，
1 2 3 7 5模上4分別是：
1 2 3 3 1
如果采用同余+dp的方法，難度會相當大，規則比較復雜；
這時，我們采用一種巧妙地方法，就是用一個sum[i]數組來記錄前i個數之和%4，例如上例中，我們得到：
|
I |
0(該列隱含) |
1 |
2 |
3 |
4 |
5 |
|
Sweet[i] |
0 |
1 |
2 |
3 |
7 |
5 |
|
Sum[i] |
0 |
1 |
3 |
2 |
1 |
2 |
由此，我們在碰到1.sum[i] == 0 或者2.sum[i]的值已經在前面出現過的情況時，就可以知道有解，并且解是從上一個出現該sum[i]數值的后一個位置開始→現在sum[i]的位置，這個貌似可以解出可能的解；但由于加和的順序隨機，所以還不清楚是否可以在該case有解的情況下一定能夠解出解。這時候，我們就要用到鴿籠原理了。
運用《離散數學與組合數學》書中的方法，我們可以把sum[1~n=nneighbor](或0~n)看做n+1只鴿子（注意上面的隱含0列），飛入c=nchild個鴿籠中，再注意到題目中有這樣的數據范圍：
The first line of each test case
contains two integers c and n (1 ≤ c ≤ n
≤ 100000) （這是本題能用鴿籠原理的最重要的前提）
由此我們可以知道一定有兩只鴿子是飛入同一個籠子當中的，所以加法的順序就自然不用考慮了；而且由這個我們也可以知道，此題一定不存在無解的情況。
代碼就不貼了，數學題還是要自己想才好（本例中（后略）是1，2，6，6），
找到第i小的數，i= 1，2，3，4...，correspondly，相對應的。
開始用線性表做，TLE了，沒注意到查詢是線性的……
后來看了參考了別人的solutions，發現了stl中的一個好東東，priority_queue
priority_queue的功能和用法可以看下 C++ STL
至于解題報告嘛，由于我也是參考別人寫的代碼，所以就不東施效顰了，貼一下：
http://www.stubc.com/thread-3511-1-2.html(這篇分析選用哪個數據結構思路比較好)
http://hi.baidu.com/leisimeng/blog/item/2a307e6110f394d78db10d02.html
P.S. 在代碼中間加了一些注釋，希望會有一些幫助。
2 #include <queue>
3 #include <algorithm>
4 using namespace std;
5
6 int M, N;
7 int a[30010], u[30010];
8
9 int main() {
10 #ifdef _DEBUG
11 freopen("in.txt", "r", stdin);
12 freopen("out.txt", "w", stdout);
13 #endif
14 int i, j, value;
15 while (scanf("%d %d", &M, &N) != EOF) {
16 // 左邊大根堆，右邊小根堆
17 // 這樣，當我們把它們看作一體時，可以保證它的有序性
18 priority_queue< int, vector<int>, less<int> > hmax;
19 priority_queue< int, vector<int>, greater<int> > hmin;
20
21 for (i = 0; i < M; i++)
22 scanf("%d", &a[i]);
23
24 u[0] = 0;
25 for (i = 1; i <= N; i++)
26 scanf("%d", &u[i]);
27
28 for (i = 1; i <= N; i++) {
29
30 // inserting a+ 0 to 1, 1 to 2, 2 to 6, 6 to 6 according to i
31 for (j = u[i-1]; j < u[i]; j++) {
32 hmax.push(a[j]);
33 /* we want to get the i-th smallest number, so when
34 * we reach i(in the big-root heap), the excessive(for
35 * ive(for now) must be in the small-root heap so that
36 * we could sort it and might use it later
37 */
38 if (hmax.size() > i-1) {
39 value = hmax.top();
40 hmax.pop();
41 hmin.push(value);
42 }
43 }
44 // after the loop, the answer is the root of the small-r heap
45 value = hmin.top();
46 hmin.pop();
47 hmax.push(value);
48 printf("%d\n", hmax.top());
49 }
50 }
51 }
52
那么
lg(x/10^y) = lg(f) lg是底為10的對數
上式可以變為 lg(x) - y = lg(f)
==> n*lg(2) - y = lg(f)
現在，只用求y即可，
其實， (int) y = lg(x) = lg(2^n) = n*lg(2),
看起來不是跟上一個相等嗎？但是注意y展開后是100000...的形式，所以我們在求出了它的對數之后，只取它的整數部分即可，即y是int型，所以……后面的不用推了，把f外面的對數符號拿過去就是了。
最后得到：
f = 10^(n*lg(2)- (int)(n*lg(2)))
同樣的，如果要求3、4、5...的n次方，只需要把2改為它們即可
P.S. 不過此算法在算2的3次方時會有誤差，還不清楚為什么？（準確地說，在冪n小的時候都有誤差）想請教一下各位大牛，謝謝啦~
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
while (scanf("%d", &n) && n!=-1) {
int y = (int) (n * log10(2.0));
double t = n * log10(2.0);
int ans = (int) (pow(10.0, t-(double)y) + 1e-8);
//n == 2 答案有誤差，在加上1e-8后，誤差消除
printf("%d\n", ans);
}
return 0;
}