一点一点前进...

0%

原题链接

首先来定义什么是$S$-number。若一个自然数$n$是完全平方数,且将$n$的十进制写法分割成2个或多个数字,这些数字之和恰好是其平方根,那么这个数字就是$S$-number。
以下都是$S$-number:

  • $\sqrt{81}=9+1$
  • $\sqrt{6724}=6+72+4$
  • $\sqrt{8281}=8+2+81=82+8+1$
  • $\sqrt{9801}=98+0+1$

$T(N)$表示所有$n\leq N$的$S$-number之和。已知$T(10^4)=41333$。求$T(10^{12})$。

遍历$i\leq 10^6$,可以得到所有$n\leq 10^{12}$的候选值,这些事可能的$S$-number,需要考虑的就是如何判断一个根$\sqrt{n}$和$n$满足$S$-number的性质。
首先,对于某个$n$,其长度是$l$,那么分割的方式总是固定的。比如$123$和$124$的分割模式是一致的,前者分别是${1,2,3},{12,3},{1,23}$,后者分别是${1,2,4},{12,4},{1,24}$。那么我写了代码遍历出所有模式,长度最多是12。$10^{12}$长度是13,但是它是$S$-number先不考虑,最后求和加上就行。

阅读全文 »

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$有多少种方式分解成两数之积。

阅读全文 »