前段时间学会了一个线性筛法，这个算法居然是O(n)的，确实令人震惊。而且更棒的是，它还为处理基于素因子分解的积性函数，提供了线性的筛法
先贴一下代码吧^^
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const int N=100000;
int prime[N+1];
int get_prime() ///get primes from 1 to N in liner time
{
memset(prime,0,sizeof(int)*(N+1));
for(int i=2;i<=N;i++)
{
if(!prime[i]) prime[++prime[0]]=i;
for(int j=1;prime[j]<=N/i;j++)
{
prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
return prime[0];
} |
算法的思路是这样的：总是使用能整除合数的最小素因子，筛去合数。注意第12行，这句话保证i不被任何比prime[j]小的素数整除，对于i*prime[j]（这个j包括比当前条件成立的j更小的j），它的最小素因子显然就是prime[j]。注意，筛去合数的，总是该合数的最小素因子和与之对应的另一个因子i，所以它只会被筛一次^^
类似的可以得到很多积性以及“和性”的函数值，比如欧拉phi函数，sigma函数（n的所有因数和），还有n的所有因子的个数，等等等等。。。
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| int ph[N+1]={0}; ///phi(x) for x<=N
int sig[N+1]={0}; ///sigma(x) for x<=N,sigma(x) is sum of x's all productors^^
int productorcnt[N+1]; ///count of productor numbers frome 1 ro N
void phi_all() ///get phi(n) from 1 to N in liner time
{
memset(ph,0,sizeof(int)*(N+1));
prime[0]=0;
for(int i=2;i<=N;i++)
{
if(!ph[i]) prime[++prime[0]]=i,ph[i]=i-1;
for(int j=1;prime[j]<=N/i;j++)
{
if(i%prime[j]) ph[prime[j]*i]=ph[prime[j]]*ph[i];
else
{
ph[prime[j]*i]=ph[i]*prime[j];
break;
}
}
}
}
int min_pk[N+1];
void sigma_all()
{
memset(sig,0,sizeof(int)*(N+1));
sig[1]=1,min_pk[1]=1,prime[0]=0;
for(int i=2;i<=N;i++)
{
if(!sig[i]) prime[++prime[0]]=i,sig[i]=i+1,min_pk[i]=i+1;
for(int j=1;prime[j]<=N/i;j++)
{
if(i%prime[j])
{
sig[i*prime[j]]=sig[i]*sig[prime[j]];
min_pk[i*prime[j]]=min_pk[prime[j]];
}
else
{
min_pk[i*prime[j]]=min_pk[i]*prime[j]+1;
sig[i*prime[j]]=(sig[i]/min_pk[i])*min_pk[i*prime[j]];
break;
}
}
}
} |
注意：得到的是从1~N之间所有数的对应函数值，而且这上面的每一个函数，都能顺便产生一个对应素数表。用一个50000大小的表，你就能处理50000的平方大小的数的对应函数值了^^
前天遇到了这么个题目：
给定一幢n层的楼，给你两个杯具，要求用最少的次数，确定杯具从能被扔碎的最低层，注意，要求最坏情况。（这是一个临界点，在这一层的下一层，把杯具扔下，落地不碎，在这一层扔下，杯具碎。。。）** 杯具碎了就不能在用了，注意，杯具只有两个^^
遇到这个问题，首先得避免二分的泥淖。。在杯具无限的情况下，二分是绝对出色的，但是在杯具有限的情况下（尤其是它少得可怜的时候），二分就杯具无限了。。
其实，通过分析解的形式，我们可以得到一个思路^^
如果第一个杯具在某一层Hb碎了，最坏我们还需要多少次才能确认在拿一层呢？注意，因为有一个杯具碎了，所以只有一个杯具了。。
这取决于，我们已知的杯具不会碎的最高层Hl，显然，我们知道杯具的临界H应该满足Hb>=H>Hl，在这里，我们最坏需要多少次找到这个值呢？答案是Hb-Hl-1次，这次，我们只能老老实实，从小到大一次一次扔了，因为如果你跳着扔的话，万一杯具碎了，你就没有杯具了，然后你失败了。。
如果我们假设最坏次数是p，我们怎么选择第一次从哪层扔呢？
答案是第一次从p层扔。显然，第p层扔碎掉是最坏次数是p(就是p-1加上刚才碎掉的那次)，容易看到，这个层数是在p的限制下，我们能取到的最大的一个。我们这个层数取的越大，剩下的层数就越少，如果在第p层没碎的话，剩下的子问题就越小
因为，我们限定了最坏次数p，而且我们已经扔了一次（在第p层），所以如果在p层没碎，问题回到一个n-p大小的子问题（之前我们知道第0层不碎，现在我们知道第p层不碎），因为我们已经扔了一次，这次我们确定一层往下扔，碎了以后，最坏代价要控制在p-1内。当然，同样的我们把这个最大化，我们在子问题的p-1层往下扔（就是p+p-1）子问题的最坏代价是p-1，总的最坏代价还是p（加上之前在原文题p层的那一次，没碎。。）
这个过程不断重复，我们得到p+p-1+p-2+...+2+1=(p+1)*p/2层，也就是最多这么多层的楼，我们能通过这种方式用p确定临界值。现在，反过来，通过楼层数解满足条件的最小的p。。条件是p(p+1)>=2n
事实上，我们平摊了最坏代价，使得最坏情况平均化了，总的最坏代价也就小了。。当然证明本身不是基于平摊的，因为平摊确实不好证明。。
最终人择原理(Final anthropic principle (FAP)): “包含智慧的资讯处理过程一定会在宇宙中出现，而且，一旦它出现了就不会灭亡。” (Barrow和Tipler，1986)——摘自wikipedia
乍一看，这样论断太不靠谱，因为有太多的因素导致生命消失，这一论断确实是不可思议的。然而，仔细一想，这一论断其实来自于Choas（混沌）：系统一旦变得足够复杂，他将不可逆转的变得越来越复杂。这一模式被打破的概率，是如同时间逆转这种事件般不可思议的事
要理解这些是“困难”的，因为来自物理的现实总会带来不必要的误导！注意以下论述：
“人择原理”最初表达：自然定律惊人地适合生命的存在。
为什么？因为生命存在，而且它已经存在！如果这一条不成立，那怎么会有生命呢？另一方面，生命总是适应于它所存在的宇宙，这也是它存在的一个原因。我们应该注意到，没错，是适应！因为我们的宇宙是这个样子的，所以有我们这样的生命，但是，宇宙的不同发展方向，将完全会导致完全不同的场景，可能是完全不同的宇宙常数，完全不同的空间，也许有完全不同的生命。
生命是适应于它所存在的宇宙的，正因为如此，我们宇宙的某些条件并不能成为生命存在的必要条件。说说我前几天还有的一个误区吧:我一直认为，生命的存在依赖于负熵。地球是一个开放系统，有源源不断的负熵输入（稳定的），这些足以维持系统内部的有序（生命）。事实上，地球上的生命也确实非常依赖于这一点。为什么呢？因为负熵给予了系统极大的活力，给予了系统足够的初始复杂度，并且，它是一个外部的进化优势。没错，地球生命适应了这一点。如果负熵的输入不存在了，生命也将能适应这一点，我毫无疑问的相信。
chaos导致，即使是一个确定的系统，也会导致不可思议的事发生。即使是基于非常简单的基本模式，也许最终也会表现出惊人的复杂。更令人不可思议的是，这种复杂会形成模式，会发生自发的组织和进化！如果你对达尔文的进化论有足够的领悟，并不难理解这一点。没错，进化论是一个典型的chaos自进化现象。复杂一旦到达这个模式，他将变得越来越复杂，这一切几乎是不可逆转的。即使出现一个突发的事件，把已有的状态打乱，也很难彻底毁灭，因为彻底把所有的复杂降到一个限度是几乎不可能的，只有上帝（如果它存在的话）才能精确定位每一个复杂系统的位置并把它完全摧毁而不论它有多小，因此复杂被彻底击垮的概率，如同时间逆转般完全不可思议。
人择在某种程度上帮助了人们揭去物理具有误导性的特性，让我们更清楚的看到世界的本质
对混沌有所不解的朋友可以看下这部纪录片——《神秘的混沌理论》（The Secret Life of Chaos）-BBC
2010吉林省赛E题Warehouse and Truck。卡车在仓库装了货物，送到各个商店（ 所有点都在一条直线上），耗费是当前载重量乘以距离（在每个商店卸下货物之后载重量发生变化）。
比赛的时候没找到算法，这题郁闷很久，一直到现在^^其实想想，当初比赛的时候连什么是DP都不知道。当时在数学上还有些癖好——根本无视递推，当时的我看来，只有通项才是有意义的-_-!确实太固执。。。
当然，我还是找到了解的形式：
显然，一旦到达一个端点，它应该一路直冲到另一端。在到达端点之前，有各种折返，但是可以确定每次折返都是越过仓库的（如果它折回来，必然是越过仓库以后再折回去的）。如上所说，这都是显然的。。。其实依照这些就可以很快导出递推，只不过当时的我对递推很不敏感，这真是杯具。
首先，折返必然是穿越仓库(x=0)的。我们令i表示仓库左边的点，j表示仓库右边的点（我想我不需要用太多晦涩难懂的数学语言来描述这一点），
我们用
表示遍历i,j范围内所有点，但不越出这个范围的最优开销（其实就是一个小的子问题，去掉了i到j外的所有点）。当然这是不够的，根据上面的解的形式，最优解必然在到达一个端点（i或者j）之后，直接转到另一个。我们需要区分两种情况：
然后这确实足够了
因为从i到j最优解必然是
的最优解末端往右到j。同样，对称的，可以得到j到i的，这样就得到了
。
这个递推，虽然描述简单，求起来却很麻烦。鉴于式子过长,代码就不贴了，因为我自己看起来都够呛（表达式很长）。这样的递推时间上是
的，其实因为是对分的，所以常数很小^^
想了下，还是把状态方程写出来。我们令
为i到j的距离，令
为剩余货物的量（就是i到j所有点的货物全部卸下之后剩下的货物），于是，我们有以下方程：
***如果递推特征不是很明显的话，或许分析解的特征，可以找到更多思路
的素数。现在考虑一个一般的形式
在什么情况下p必为合数？
能被a+1整除。如果考虑置换
，注意到