Project Euler 096~100
关于啥是Project Euler 详见 https://projecteuler.net/about
观前声明：
这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码； 各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。
大佬看到了笑笑就行，还请轻喷。
带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）
语言是c++，用的VS平台
100题啦.完结撒花，
o 还有600多道a 那没事了.
再次介绍一下欧拉计划. 这是个有着许多数学相关问题的网站，且每周都会更新一道题
大部分题都需要灵活的数学思维与编程技巧结合才能有效的解决.
我去做pe 仅是因为能够享受思考与实现算法乐趣.甚至过程中还能被题目科普些新知识
如果您仅是来搜寻答案的话.那我觉得duck不必，解决的过程中的乐趣是无可替代的
pe的前100道题是新手教程题 更完这期后以后可能咕了 也可能哪天闲着继续更.看心情随意更新
那么，开始最后的5道水题吧
Su Doku
Problem 96
Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.
A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.
The 6K text file, sudoku.txt,contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).
By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.
sudoku.txt：https://projecteuler.net/project/resources/p096_sudoku.txt
不会有人没玩过数独吧？？？？？
9×9网格内每行每列每宫格（从左到右从上到下有9宫）的数字只能出现1次
例子的图左非0数字是已给出数字，0是待填数字，图右为数独的解
数独的魅力在于其是唯一解性的
上面这个网址里包含了50道数独题，求每个解出的数独题网格左上角的三位数之和，比如例图的右图就是483。
作为一位资深数独爱好者，50道我都是用笔纸过的.
编程模拟数独求解网上好像已经有很多模板了，大抵思路都是一个数字一个数字的填，填错了就回溯修改. 比较实用的是宫回溯法，就是一宫填完后去下一宫填，这样更容易发现错误的数字，效率会高很多。
我前年的时候无聊尝试实现了，被同学谑称为“打印机回溯法”，思路是从左到右从上到下按1~9的顺序逐个填入可能的数字，如果当前位置填i出错误，就将i换成i+1，如果直到i=9都是错的，那么回溯至上一个格子，将之变换为下一个数字，如果再不行继续回溯。以此类推，事先标记已给出的数字。
这个算法颇有些羞于见人. 不过是最常见的思维和最暴力的实现罢了，我也见过有的人将之当作线性规划问题赋予01变量来求解的，未尝不是一种思路。
由于数独相关算法 前人之述备矣，所以就不多提了，各位自己尝试更好的思路实现吧。
ans：24702
Large non-Mersenne prime
Problem 97
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.
Find the last ten digits of this prime number.
梅森素数是形如2^p-1的素数（p为素数）
第一个超过一百万位的素数是在 1999 年发现的，并且是一个梅森素数： 2^6972593−1;
它包含2098960 位。之后包含更多位的，形如2^p-1的梅森素数被陆续发现。
在 2004 年人们发现了一个包含 2357207位的非梅森素数：28433×2^7830457+1
求出这个素数的最后十位。
最后10位，意味着计算只需保留后10位.
用乘法模拟指数，每次计算后取模即可，算是白给题了，不用快速幂都很快.
代码较为简单不放了 一个循环的事.
ans：8739992577
Anagramic squares
Problem 98
By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36^2. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96^2. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.
Using words.txt , a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).
What is the largest square number formed by any member of such a pair?
NOTE: All anagrams formed must be contained in the given text file.
words.txt：https://projecteuler.net/project/resources/p098_words.txt
用完全平方数 36^2=1296 来表示单词 CARE （C=1，A=2，R=9，E=6）
并取它的全排列可以得到另一个单词RACE=9216=96^2
将 CARE（和 RACE）叫做一个平方变位词对，并规定前置的 0 是不允许的，同时也不允许不同的字母用相同的数字替换。
words.txt 文件内有近2000个单词，找出其中所有的平方变位词对（一个回文单词不被认为是它自己的变位词）。
这些变位词对中能形成的最大的平方数是多少？
注：所有的变位词必须是文件中包含的单词。
经典模拟搜索实现类.
可以先对这个文件预处理一下，看看这之中最长的单词。
文本中最长的单词为14个字母：ADMINISTRATION，所以可确定平方数(n^2)n的上界为9938090 （因为这个单词最大赋值为98765643293615.开跟取整后为9938090）
大体思路就是对于每个单词，找单词表中有没有其他不同排列但字母相同的单词，如果有，对这样的每个其他排列单词，先找原单词的每个能匹配的平方数，然后将每个字母对应的数字储存，再把每个其他排列的单词对应的数字弄出来，检验其是否为平方数，如果是那么动态储存两个平方数中的大者给maxn，跑完所有其他排列单词和每个其他排列单词能对应的匹配平方数，就能得到该原单词所能得到的最大平方数，都莫得就返回0；
再在主函数用这个思路遍历所有的单词，找到最大的maxn
基于编了个略有些冗杂的代码：
总的来说是一道不是很难的模拟题.做完后也没啥感觉.
ans：18769
Largest exponential
Problem 99
Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.
However, confirming that 632382^518061 > 519432^525806 would be much more difficult, as both numbers contain over three million digits.
Using base_exp.txt , a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.
NOTE: The first two lines in the file represent the numbers in the example given above.
base_exp.txt ：https://projecteuler.net/project/resources/p099_base_exp.txt
base_exp.txt 包含一千行内容，每一行都包含一个基和一个指数，找出哪一行具有最大的值。
...
99题，作为破百撒花前的最后一道题...
水题，抬走，下一道！
取对数随便比较. 主函数动态替换最大值即可
709行的895447^504922是最大值。
ans：709
Arranged probability
Problem 100
If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.
The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.
By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.
如果一个盒子里有 21 个有色的碟子，15 个蓝色的和 6 个红色的。从中随机取两个，可知取到两个蓝碟子的几率是 (15/21)×(14/20) = 1/2.
下一个满足此条件（即随机取两个碟子的情况下取到两个蓝色碟子的几率是 50%）的情况是 85 个蓝碟子和 35 个红碟子。
对于包含超过10^12个碟子的情况中，满足上述条件的并包含最少碟子的情况，该情况下共需要多少个蓝碟子？
写成代数分析一下.用x表示蓝碟子数，n表示总碟数
1/2=x(x-1)/(n(n-1))
即2x(x-1)=n(n-1)，变化一下：2(2x-1)^2=(2n-1)^2+1
令a=2x-1,b=2n-1，2a^2=b^2+1
即为b^2-2a^2=-1 观察之后发现这是个pell方程的变式.
是不是意外的很熟悉..66题的丢番图变式...
先找到最小整数解：
那么对于原佩尔方程b^2-2a^2=1 D=2
用66题的连分数展开易知根号2的连分数为[1:(2)]
b^2-2a^2=1的最小正整数解为b=3,a=2
并且易知，若b,a为前一个方程的解，D为素数时（则a,b必一奇一偶不妨令b为奇数a为偶数），那么令u^2=(b-1)/2 v^2=(a+1)/2D
2uv=b 则（u,v）为后一个方程的最小整数解
再整理一下得到如果把根号D的第一个循环节写出来，对应的p/q就是b^2-2a^2=-1的解 根号2的第一个循环节对应的p,q为1/1，所以1,1就是其最小正整数解；
对于方程：Ax^2+Bx-Cy^2+Dy+E=0，
有形如
X(n)=aX(n-1)+bY(n-1)+c;
Y(n)=dX(n-1)+eY(n-1)+f
的通解。
所要做的只是需要根据前几组解，把a,b,c,d,e,f计算出来，然后循环求通解即可。
可以先跑出几组解（循环搜索满足b^2-2a^2=-1的数）
第一组解：1，1
第二组解：5，7
第三组解：29，41
第四组解：239，169
易知对于这道题若b^2-a^2=-1
那么a(n+1)=2bn+3an b(n+1)=3bn+4an
循环递推即可得到答案.
ans：756872327473
完结撒花.通过教学关了，希望各位能有所收获。100题后就出新手村了o~
后续的更新嘛... 先失踪个1年左右再说吧.
