Project Euler 057~060
关于啥是Project Euler 详见 https://projecteuler.net/about
观前声明：
这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。
大佬看到了笑笑就行，还请轻喷。
带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）
语言是c++，用的VS平台
Square root convergents
Problem 57
It is possible to show that the Square root of two can be expressed as an infinite continued fraction.
By expanding this for the first four iterations, we get:
The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?
根号2的连分数展开如上（连分数的概念以后的题有机会细说.对这道题只要当作数列然后找规律就能解决）
1，3/2，7/5，17/12...
问前1000项内有多少项是分子的位数大于分母的？
如果纯当成找规律的数列（事实上我也是这么做的），不难发现如果上一项是x/y，下一项便是(x+2y)/(x+y) 那么只要根据这个规律分开写出前1000项的分子分母即可.
对于c++而言唯一不便的地方就只有项数大了之后爆了需要用大整数加法而已.
大整数加法已经提及多次不再详述（详见13题）
我这里使用fracde[n][]表示第n项的分母（数组形式），fracnu[n][]表示第n项的分子
其他就是递归使用大整数加法.（getfraction函数）
不展开细究背后的连分数的话，这题也就是个水题了；但因为之后会遇到 所以我就不细说了.
ans：153
Spiral primes
Problem 58
Starting with 1 and spiralling anticlockwise in the following way, a Square spiral with side length 7 is formed.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
It is interesting to note that the odd Squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a Square spiral with side length 9 will be formed. If this process is continued, what is the side length of the Square spiral for which the ratio of primes along both diagonals first falls below 10%?
以自然数旋转生成的7×7矩阵中，在对角线的13个数中，有8个质数，比例是8/13≈62%
那么如果这个矩阵不断生成下去，到边长为多少时这个比例会首次降至10%以下？
水题.
边长为n的螺旋正方形对角线有2n-1个数字，所以只要检验3,5,...,n边框上的3个数字是否为素数，再加起来最后除以2n-1就能获得比率。
显见边为n的正方形的3个带检验数（x1,x2,x3）为：
x1 = n * n - n + 1, x2 = x1 - n + 1, x3 = x2 - n + 1;
质数检验用最朴实的因子检验（o(n^1/2)）即可
为了方便，可在全局设一个数组记录边为n时该边的质数个数，Square[n]=0或1或2或3，上限设置的大一点就不怕跑不到.
ans：26241
XOR decryption
Problem 59
Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.
A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.
For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.
Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.
Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.
p059_cipher.txt：https://projecteuler.net/project/resources/p059_cipher.txt
这是一道密码学相关的题，它是目前我在pe中见过的最浪漫最酷的题。
虽然这里只是简单的用异或运算进行加密
姑且说下异或加密规则：
异或加密就是将明文字符对应的ascii码值与密钥字符对应的ascii码值相异或把得到的ascii码值对应的字符作为密文，从而实现加密。对于明文长度长于密钥的情况，则循环使用密钥对明文进行加密，如明文为I am happy（包括空格10个字符），密钥为key，加密时应将明文与keykeykeyk一一对应进行异或，需注意这里空格也有对应的ascii码，加密的时候如果是对整个明文直接进行加密，空格也会被加密。
题设给了我们一个已经被加密的文件并告知密钥为3个字符，文件里是加密后的ascii码值，我们的任务就是破解加密的文件，还原文本后，将原文本所有的ascii码值相加得到答案。
关于这题，有个很简单的思路，这也可以作为以后频率分析的启蒙。
有1455个数，跑几遍后可以获得以下信息：最大值为95。
密钥为3个字符，将密文的第0 3 6 9 ..划为一组，第1 4 7 10...划为一组，第2 5 8 11...划为一组，分别找到每组中出现次数最高的数字，将这个数字和空格的ascii码32相异或，得到密钥。
关于频率分析，有位up已经针对此题写了篇不错的专栏 (@穆罕默德-李)
https://www.bilibili.com/read/cv7078915有比我更为详尽的分析 还引经据典的扩展了背景，有兴趣者不妨去看看。
我首先将这些数字放在数组A[]中，然后先分组 跑一遍看3组中哪3个数字出现最多：
这样跑一遍之后分别得到3组中频率最高的为：69 88 80
与32（空格的ascii码）异或后分别得到101，120，112；（对应exp）
再将下述放入上面的主函数中便可直接算原文本的ascii码
int sec1 = (max1i ^ 32), sec2 = (max2i ^ 32), sec3 = (max3i ^ 32), sum = 0;
for (i = 0; i < 485; i++)
{
sum += (A1[i] ^ sec1);
sum += (A2[i] ^ sec2);
sum += (A3[i] ^ sec3);
}
cout << sum;
但...都做到这个地步了怎么可能不输出原文本是啥
转码也很简单 异或回去后直接char()那个数值就能变为字符，逐个输出即可
转码代码：
char s[1455];
for (i = 0; i < 485; i++)
{
A1[i] = (A1[i] ^ sec1);
A2[i] = (A2[i] ^ sec2);
A3[i] = (A3[i] ^ sec3);
}
for (i = 0,j1=0,j2=0,j3=0; i < 1455; i++)
{
if (i % 3 == 0)s[i] = char(A1[j1++]);
if ((i - 1) % 3 == 0)s[i] = char(A2[j2++]);
if ((i + 1) % 3 == 0)s[i] = char(A3[j3++]);
}
for (i = 0; i < 1455; i++)
cout << s[i];
原文：
An extract taken from the introduction of one of Euler's most celebrated papers, "De summis serierum reciprocarum" [On the sums of series of reciprocals]: I have recently found, quite unexpectedly, an elegant expression for the entire sum of this series 1 + 1/4 + 1/9 + 1/16 + etc., which depends on the quadrature of the circle, so that if the true sum of this series is obtained, from it at once the quadrature of the circle follows. Namely, I have found that the sum of this series is a sixth part of the Square of the perimeter of the circle whose diameter is 1; or by putting the sum of this series equal to s, it has the ratio sqrt(6) multiplied by s to 1 of the perimeter to the diameter. I will soon show that the sum of this series to be approximately 1.644934066842264364; and from multiplying this number by six, and then taking the Square root, the number 3.141592653589793238 is indeed produced, which expresses the perimeter of a circle whose diameter is 1. Following again the same steps by which I had arrived at this sum, I have discovered that the sum of the series 1 + 1/16 + 1/81 + 1/256 + 1/625 + etc. also depends on the quadrature of the circle. Namely, the sum of this multiplied by 90 gives the biquadrate (fourth power) of the circumference of the perimeter of a circle whose diameter is 1. And by similar reasoning I have likewise been able to determine the sums of the subsequent series in which the exponents are even numbers.
这是欧拉在解决平方无穷级数和的问题∑1/(k^2)=（π^2/）6的一篇论文中的选段。
（关于这个问题自行搜索. 证明会用到泰勒展开 根的分析等 或直接去阅读欧拉本人的《无穷分析引论》也可）
在破解出原文的那刻，以我粗浅且稀缺的词汇，我只能说，这道题简直浪漫到死好吗！
ans：129448
Prime pair sets
Problem 60
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
3，7，109，673这个4质数集合具有非凡的性质，不论如何组合它们，37，73，7109，1097...等等 都会得到一个新的质数，它们的和792代表了具有这个性质的且和最小的4素数集合。找到具有这样的性质最小的5素数集合，并求出它们的和。
事实上 我第一个思路就是完完全全的暴搜，先跑出一定范围的质数保证5个素数都在其中（实际上这个和很小 才5位数），然后两两相接检验（数化数组相接，数组化数检验）
然后写了个非常丑还要跑很久的代码（好像跑了几小时跑出来了）：
getprime函数中Bprime获得一个顺序排列的全是素数的数组（埃氏筛）；
check函数检验2个素数是否符合性质
check5n函数利用check函数检验5个
然后是不忍直视的主函数...用a b c d e代表质数序号，暴搜找...
关于优化部分，可以直接在素数中分组，比如把这些素数分成mod3余1和余2的2组，然后在2组内分别找（因为任取2组中各一个相加都会是3的倍数，所以首尾相接必定不是素数）：
这样会快一点
void getmod12(void)
{
for (int i = 0, j1 = 0, j2 = 0; Bprime[i] != 0; i++)
if (Bprime[i] % 3 == 1)B1prime[j1++] = Bprime[i];
else B2prime[j2++] = Bprime[i];
}
别的优化还有类似计算一次记录一次，比如abcde不符合，则之后不会再判断出现ab,ac,ad,ae,bc,bd,be,cd,ce的情况等等.
但我既然都跑完了 就懒得优化了...优化部分自己写吧。
质数分别为 13，5197，5701，6733，8389
ans：26033
（实际上除了60是20%的难度，其余3道都是5%..）
后续随缘更新.
