ProjectEuler-419-421
好久没写东西了，都长草了。
上一个月也比较忙（借口），四处旅游中。
7.22 正式离校，走之前和谢老师吃了顿饭，然后给新高一小朋友讲十天的课吧收获 1k 。
然后去珠海参加西山居的比赛。不得不说西山居很良心，居然是考算法，TC 形式。没有看错题以及没有 FST 导致最后混了个 #2 还是不错的。收获 Surface PRO 128G 一台。最后送了老爸。
然后去西安旅游。去之前以为西安不好玩，一下子就可以玩完的，去了之后发现开始可以玩很多东西的，走的时候发现还有好多地方想去玩。
然后去郑州骗钱。骗完钱后就在郑州玩了就几天。说实话郑州不好玩，所以我的“郑州游记”非常搞笑：第一天手机上不了网，于是就不敢出去了；第二天原本准备去少林寺玩玩，结果这天要多校，前面坑了好多次的队友了，有点过意不去了，所以做多校去了 →→ ；第三天由于 wxd、gzp 在，最后 vani 也来了，还来了个专注搞笑的，本来以为会去各个地方玩玩的，但是最后上午聚齐的时候已经十二点了，就直接吃饭去了。下午就在 KTV 唱了两个小时的歌……然后我的郑州之旅到底到了几个地方 →→
现在在贵阳旅游，闲着无聊做了两个题 →_→
ProjectEuler-419
Problem
look and say 序列是这么个东西：第一个元素是 1 ；第二个元素是 11 ，表示上一个元素是 1 个 1 ；第三个元素是 21 ，表示上一个元素是 2 个 1；接下来几个分别是 1211, 111221, 312211, 13112221, 1113213211 。易知每个元素只包含 1、2、3 三个元素。求这个序列第 \(10^{12}\) 个元素中 1、2、3 的个数。答案取模。
Solution
以前只听说过这个序列，对它的性质一无所知……一开始往 DP 上面想，死活想不到状态。
但是我听说过一个常数叫做 Conway 常数，指的是这个序列的长度会不断递增，而且相邻两项的长度比会逼近一个常数，这个常数就是 Conway 常数。
这其实就是个提示。考虑一个序列，相邻两项比逼近一个常数，第一想法就是线性齐次递推式。然后就开始找关于 Conway 常数的资料。发现 Conway 常数是某个 71 次方程的唯一正实数解，那应该就是一个线性齐次递推式了。而且可以找到这个方程，但是对于求每个数字出现的次数感觉没啥帮助 →_→
继续找 Conway constant 的资料，然后就找到了一个神奇的定理： Cosmological Theorem 。这个定理讲的是 look and say 序列从第 8 项开始，每个元素就可以分成若干份，使得每一份都是某 92 份中的一个。相关资料： Wolfram 和 一个奇怪的网站
……我想你大概懂了。预处理出所有的 92 个基本子串，求出每个子串一次变换后会产生哪些子串。这就是一个矩阵乘法。求出每个子串出现的次数后一切就没了。
……不给我 Google 这题能做？
……不给我 Google 这题能做？
……不给我 Google 这题能做？
ProjectEuler-421
Problem
定义 \(s(n, m)\) 表示 \(n^{15}+1\) 的所有不同的小于 \(m\) 的质因子的和。例如 \(2^{15} + 1 = 3^2 \times 11 \times 331, s(2, 10) = 3, s(2, 1000) = 345\) 。
求 \[\sum_{n \leq 10^{11}} s(n, 10^8)\]
Solution
这个题被 dyh 拿来做 ZJOI 讲课用，但是当时给我看课件的时候我还不会 2333
对于一个素数 \(p\) ，我们的目标是求出有多少个 \(n\) 满足 \(p | (n^{15}+1)\) 。这相当于要求 \(n^{15} \equiv -1 \mod{p}\) 。令 \(g\) 为 \(p\) 的原根，可得 \(g^{\frac{p-1}{2}} \equiv -1 \mod{p}\) ，所以如果 \(n \equiv g^x \mod{p}\) ，有 \(15x \equiv \frac{p-1}{2} \mod{p-1}\) 。这是一个很简单的同余方程，解的个数为 \(gcd(15, \frac{p-1}{2})\) 。求出所有解后可以算出有多少个 \(n\) 满足要求。
似乎很简单的样子可我为啥当初就不会呢。
nonsense
Bootstrap3 发布了。这个模板里面有很多不兼容，哪天改改（flag 立的飞起）。
谁来证明下这个式子： \[\sqrt{1+2 \sqrt{1+3 \sqrt{1 + 4 \sqrt{1+ \dots}}}} = 3\]
我想了下，觉得比较显然，可就是 YY 不出一个严谨的证明。