Problem 88

一个自然数$N$如果能被至少两个自然数集合${a_1,a_2,\cdots,a_k}$同时用乘积和和表示，即$N=a_1+a_2+\cdots+a_k=a_1\times a_2\times\cdots\times a_k$，那么称为Product-sum number。
比如$6=1+2+3=1\times 2\times 3$。
给定一个固定大小$k$，可以找到一个最小的$N$是Product-sum number。对于$k=2,3,4,5,6$，最小$N$如下
$$\begin{aligned}
k=2:&&&4=2\times 2=2+2\
k=3:&&&6=1+2+3=1\times 2\times 3\
k=4:&&&8=1\times 1\times 2\times 4=1+1+2+4\
k=5:&&&8=1\times 1\times 2\times 2\times 2=1+1+2+2+2\
k=6:&&&12=1\times 1\times 1\times 1\times 2\times 6=1+1+1+1+2+6
\end{aligned}$$
因此$2\leq k\leq 6$，最小Product-sum number$N$之和是$4+6+8+12=30$，注意8只记录一次。
求$2\leq k\leq 12000$时，最小Product-sum number的$N$之和。

题目链接

类似24点游戏，使用数字$1,2,3,4$、运算符$+,-,*,/$和括号能够得到不同的正整数。对于数字的限制是每个数字只能使用一次，且不能将数字连起来用，比如12、34。
比如
$$8 = (4 * (1 + 3)) / 2$$
$$14 = 4 * (3 + 1 / 2)$$
$$19 = 4 * (2 + 3) − 1$$
$$36 = 3 * 4 * (2 + 1)$$
使用数字$1,2,3,4$可以得到31个不同的数字，最大值是36，1-28是连续的，直到29是第一个不能通过算术表达式得到的数字。
求四个不同的数字$a<b<c<d$，能够得到最长连续的$1\to n$。

我读了 Bjarne Stroustrup 在 programming principles and practice using c++ 2nd 关于 People 的论述，觉得大师总结的很全面、很完善，遂整理如下，加入一点我的注解、想法。

98题链接

将单词CARE的每个字母替换成1，2，9，6，得到一个平方数$1296=36^2$，更重要的是，RACE对应字母也换成这几个数字，又能得到一个平方数$9216=96^2$。那么这两单词被称为平方变位单词对（a square anagram word pair）。平方数不能是0开始的，不同的字母不能有相同的数字。
题目给出了一系列单词，要求所有的单词对都从这些单词里面取得。求单词对的最大平方数。

Problem 329

一只懂质数的青蛙站在编号为1-500的方块内，它等概率的向左或者向右跳，当然不能出1-500这些方块，如果到达了边缘就只能向另外一个方向跳。
如果方块的编号是质数，那么有2/3的概率呱出 ‘P’ (PRIME)，1/3的概率呱出 ‘N’ (NOT PRIME)；反之如果编号不是质数，那么呱出’P’和’N’的概率分别是1/3和2/3。
如果它从随机的一点出发（等概率），发出 ‘PPPPNNPPPNPPNPN’ 的概率是多少呢？使用最简分数给出答案。

题目链接

分子小于分母的分数被称为真分数。比如$d=12$，那么有11个真分数
$$\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{5}{12},\frac{6}{12},\frac{7}{12},\frac{8}{12},\frac{9}{12},\frac{10}{12},\frac{11}{12}$$
其中分子分母不能约分的分数成为最简分数，用$R(d)$来表示最简分数的个数与$d-1$之比，比如$R(12)=\frac{4}{11}$，事实上，$d=12$是最小的整数满足$R(d)<\frac{4}{10}$的。
求最小的$d$，使得$R(d)<\frac{15499}{94744}$

原题链接

首先来定义什么是$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}$是不同的选择。问一共有多少种不同的选择方式。

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之和。