0%

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 不出一个严谨的证明。