Project Euler 061~063
关于啥是Project Euler 详见 https://projecteuler.net/about
观前声明：
这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。
大佬看到了笑笑就行，还请轻喷。
带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）
语言是c++，用的VS平台
Cyclical figurate numbers
Problem 61
Triangle, Square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
Square P4,n=n^2 1, 4, 9, 16, 25, ...
Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, ...
The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
Each polygonal type: triangle (P3,127=8128), Square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.
This is the only set of 4-digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, Square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
3角形数到8角形数如下：
P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
P4,n=n^2 1, 4, 9, 16, 25, ...
P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
P8,n=n(3n−2) 1, 8, 21, 40, 65, ...
8128, 2882, 8281这3个4位数形成的集合有3个有趣的性质：
每个数的后2位是另外其中1个数的前2位 且刚好形成一个循环。
他们正好分别属于3，4，5角形数中的一个：(P3,127=8128)(P4,91=8281)(P5,44=2882)
这是唯一一组具有此性质的4位数。
现在要找到也具有1性质（首尾形成循环）的由6个4位数形成的一组数，它们要正好按顺序分别属于3~8角形数，并求出它们的和。
神奇.
首先稍稍分析一下，因为只要求找4位数，所以我们可以先获得3~8角形数中所有的4位数，并储存在6个数组中。（可以用P[i][j]储存，代表i角形数的第j个序列的数）：
total[i]记录i角形数的角形数总数;
思路有很多，可以直接无脑用for暴搜，或者把6个4位数拆成12个部分，直接令它们两两相等，再去判断它们是否是P3~P8，这里仅给出递归深搜的写法；
利用5个数组构建递归深搜DFS的算法：
从三角形数开始，遍历每个三角形数；
每一次深搜都会在外部用数组记录当前备选的数。(findx[]数组)（61行与73行）
若当前遍历到n角形（8>n>3）（外部的found[]数组记录当前在深搜哪一角形），会与最新的备选数（上一个已选角形数）匹配（68行至71行）
即满足前者的后2位与后者的前2位想等即匹配成功，存入备选数组然后递归搜下一个角形
但这个深搜是放在循环中的，即若下一个角形至最后没有找到的话，这里会接着向后找能与上一个角形数匹配的当前角形数；（70行至77行）
若遍历到8角形数时则会与第一个备选角形数（3角形数）匹配（48至57行）
若匹配成功则直接输出。
主函数直接调用getP()和DFS(3)即可。
6个数分别为8256, 5625, 2882, 8128, 2512, 1281
ans：28684
Cubic permutations
Problem 62
The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube.
345的立方的全排列能得到3个立方数（包括本身） ：345^3 384^3 405^3
345的立方是全排列能得到3个立方数的最小的立方数
找到全排列能得到5个立方数的最小的立方数。
不知道具体的上限所以求稳姑且先用了大整数；
在29题的时候用大整数乘法写了个大整数简易的指数运算，用来算3次方刚刚好
29题指路..（对应下面的expo函数）全排列和数化数组数组化数不多讲，为了缩小范围不妨先跑一遍所有3位数的3次方，会发现莫得（这部分自己验证撒） 并且4位数的一下能找到4个
所以姑且先将范围界定在4位数，先用一个数组cube[10000][10000]获得所有4位数的3次方并以数组形式存在cube[n][]里（cube[n][]代表4位数n的逆序排列）
判断全排列是否相同可以用另2个数组储存逆序然后都sort排序一下直接比较
在主函数中调用getcube()函数然后用5个for循环搜索即可（主函数较为狰狞 不放了）
大概2min能跑出来（还是比较慢了
5个4位数：
5027 7061 7202 8288 8384
ans：127035954683
Powerful digit counts
Problem 63
The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the 9-digit number, 134217728=8^9, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
16807=7^5是个5位数，同时也是5次方数，134217728=8^9是个9位数同时也是9次方数
有多少个n位数同时也是n次方数？
这道题可以自己拿计算机确定范围然后数出答案...
稍稍说下分析：
显然，如果一个x位数（除了1外，1=1^1）能表示成n的x次方，2<=n<=9；
9^21次方还是个21位数，9^22以上的x就不是22位数了。所以对9而言上限是9^21，且从11位数起，8^11是10位数，所以从11位数到21位数只有9能满足9^x是x位数，即11~21位数只有 11个 数字满足x位数=n^x；
以此类推可知7从7位数开始7^x不再为7位数，即7~10位数只有8，9能满足x位数=n^x，即7~10位数有4×2= 8个 数字满足；
6从5位数起...即5~6位数只有7，8，9... 有2×3=6个数字；
5从4位数起 4位数只有6，7，8，9 有4个数字；
4从3位数起 3位数只有5，6，7，8，9 有5个数字；
3从2位数起 2位数只有4，5，6，7，8，9 有6个数字
1位数有 1~9 9位数字；
综上有49个数字。
ans：49
（难得白给）
最近不定期随缘更新.
