一点一点前进...

0%

Problem 90

给两个骰子,每个骰子每面可以有不同的数字(0-9)。将这两个骰子并排摆放可以组成一个两位数。仔细挑选骰子上的数字,那么这俩骰子可以摆出所有一百以内的平方数$01, 04, 09, 16, 25, 36, 49, 64, 81$。比如一个骰子上的数字是${0, 5, 6, 7, 8, 9}$,另一个是${1, 2, 3, 4, 8, 9}$。6和9上下颠倒看起来是一样的,所以骰子上的数字如果是${0, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 6, 7}$的话,也是满足条件的。我们不关心数字的顺序,所以${1, 2, 3, 4, 5, 6}$和${3, 6, 4, 1, 2, 5}$是同一种选择,但是${1, 2, 3, 4, 5, 6}$和${1, 2, 3, 4, 5, 9}$是不同的选择。问一共有多少种不同的选择方式。

阅读全文 »

进程就是运行中的程序。

操作系统通过虚拟化CPU来提供了一种假象:仿佛有无数的CPU似的。操作系统让一个进程只运行一个时间片,然后切换到其他进程。这就是时分共享(time sharing)技术。操作系统会通过一些低级机制(比如上下文切换)和高级策略(比如调度策略)以高效地实现虚拟化。

阅读全文 »

操作系统(Operating System, OS)复杂确保系统易于使用且正确高效地运行。
操作系统主要利用虚拟化(virtualization)的技术,将物理资源(如处理器、内存、磁盘等)变得更通用、更强大、更易于使用,所以有时也将操作系统成为虚拟机(virtual machine)。
操作系统也提供很多接口(API) - 系统调用(system call) -让程序调用来访运行程序、访问内存和设备,进行其他操作等,换句话说,操作系统为应用程序提供了一个标准库(standard library)。
由于共享,操作系统需要管理(manage)这些系统的资源(resource),如CPU、内存、磁盘等,所以操作系统也是一个资源管理器(resource manager)。

阅读全文 »

Problem 86

小蚂蚁从立方体的一点走最短距离爬到对顶点,爬过的长度可能是整数,比如立方体三维分别是6,5,3,那么最短距离是10,但也不总是整数。
对于三边最长是$M\times M\times M$的立方体,当$M=100$时,有2060个边长均为整数的不一样的立方体,其蚂蚁爬过的最短距离是整数,而$M=99$时,有1975个不同的立方体。
求立方体个数超过一百万时$M$的最小值。

其实这个题目不难,关键点在于不需要计算出具体满足题意的值,只需要计数即可。
不妨设$M=a\geq b\geq c$,那么$2\leq b+c\leq 2a$,斜边长是$\sqrt{a^a+(b+c)^2}$,如果斜边长是整数,那么$b$和$c$可以在一定范围内变化。$b$最小也就是$b+c$的一半或者一半加一,最长的话就是等于$a$,同时要满足$c\geq 1$。所以很容易通过某个给定的$a$来得到满足条件的个数。

阅读全文 »

700题链接

先瞎扯一句,欧拉项目网站的第700题(整百哦)有纪念欧拉意味,看得出来,出题人很有情怀。

欧拉(Leonhard Euler)出生于1707年4月15日。
考虑序列$1504170715041707n \mod 4503599627370517$。
在这个序列的元素,如果小于前一个Eulercoin,那么它就是Eulercoin。
显然第一个Eulercoin是1504170715041707,也是序列的第一个数;该序列的第二个数3008341430083414比上一个Eulercoin大,它不是Eulercoin,第三项8912517754604比第一项小,所以是新的Eulercoin。
求所有Eulercoin之和。

阅读全文 »

原题链接

$2^7=128$是第一个以12开头的2的幂次数。下一个是$2^{80}$。
$p(L,n)$表示满足$2^j$以$L$开头的第$n$个$j$的值。所以$p(12,1)=7$,$p(12,2)=80$。
题中给出$p(123,45)=12710$以验证程序。
求$p(123,678910)$。

$2^{12710}$就是一个比较大的数字,如果使用BigInteger.ToString检查其是否以123开头还好,但是这才第45个以123开头的幂次,第678910个满足条件的幂次要大的多得多,时间也要长太多,所以我们需要一个速度更快的方式来检查。

阅读全文 »

题目链接

$s(n)$的定义是数字之和是$n$的最小值,比如$s(10)=19$。
$S(k)=\sum_{n=1}^ks(n)$,题中给出$S(20)=1074$,可以用于检测程序是否基本正确。
$f_i$是斐波那契数列。
问题是求$\sum_{i=2}^{90}S(f_i)$模1000000007。

斐波那契数列以指数速度增长,所以暴力法肯定是不行的($f_{90}$快接近long的表示上限了),那么需要在常数或者对数时间复杂度的算出$S(k)$的算法。
$s(n)$其实很容易想,数字最小,那么就是高位的值越小越好,那么低位的值都是9即可。
有了$s(n)$,我们就可以推导一下$S(k)$了。

阅读全文 »

100题链接

正整数方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$。如果$n=1260$,那么有113个不同的解,这个解的数量超过100的最小的$n$值。
求不通解的数量超过4百万的$n$的最小值。

$x$和$y$必须大于$n$,否则$1/x$或$1/y$就比$1/n$大了。所以不妨令$x=n+a,y=n+b$,其中$a,b$也都是整数。带入原式,我们可以得到$n^2=ab$。所以原方程就变成了$n^2$有多少种方式分解成两数之积。

阅读全文 »

95题链接

28有4个不包含自身的因数1 2 4 7,其和恰好是28,我们称之为完美数。
220不包含自身的的因数之和是284,284不包含自身的因数之和是220,形成了一个长度为2的链,也称之为亲和数。
从12496能形成一个长度为5的链:12496 -> 14288 -> 15472 -> 14536 -> 14264 (-> 12496 -> …)。
找到一个所有数值都不超过一百万的最长的链,问其中最小的数。

首先,我们要快速找到每个数对应的因数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var numberToDivisorSum = new List<int>(MAX + 1);
for (int i = 0; i <= MAX; i++)
{
// 1 is divisor
numberToDivisorSum.Add(1);
}

// i is a factor
for (int i = 2; i <= MAX / 2; i++)
{
// excluding the number itself, so j starts from 2
for (int j = 2; j <= MAX / 2; j++)
{
if (i * j > MAX)
{
break;
}

numberToDivisorSum[i * j] += i;
}
}

接下来计算每个数开始能够形成的链的长度,找到最长链所对应的最小的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
var numberToLength = new List<int>(MAX + 1) { 0 };
int longest = -1;
int index = -1;
for (int i = 1; i <= MAX; i++)
{
numberToLength.Add(0);
if (numberToDivisorSum[i] != -1)
{
int length = GetChainLength(i, numberToDivisorSum);
numberToLength[i] = length;
if (length > longest)
{
index = i;
longest = length;
}
}
}

private static int GetChainLength(int number, List<int> numberToDivisorSum)
{
var chain = new List<int>();
int cur = number;
while (true)
{
chain.Add(cur);
int next = numberToDivisorSum[cur];
if (next > MAX || next == -1)
{
foreach (var s in chain)
{
if (s > number)
{
numberToDivisorSum[s] = -1;
}
}
return -1;
}

if (chain.Contains(next) && number != next)
{
return -1;
}

if (next == number)
{
foreach (var s in chain)
{
if (s > number)
{
numberToDivisorSum[s] = -1;
}
}

return chain.Count;
}

cur = next;
}
}

这里有一个有点trick的地方,如果一个链形成了(已经知道最小数了),或者因数之和比MAX要大导致无法形成一个链,那么把当前number之后的数都标记一下,在外层调用函数的for循环里面跳过,这样子大概能节省10%的时间吧。