Project Euler 061~063
關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about?
觀前聲明：? ? ?
這是個(gè)人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼；各個(gè)方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??
大佬看到了笑笑就行，還請輕噴。
帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個(gè)人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因?yàn)槭窃缦葘懙乃云鋵?shí)是在各種意義上公開處刑和吐槽自己 并嘗試補(bǔ)救優(yōu)化）
語言是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角形數(shù)到8角形數(shù)如下：
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個(gè)4位數(shù)形成的集合有3個(gè)有趣的性質(zhì)：
每個(gè)數(shù)的后2位是另外其中1個(gè)數(shù)的前2位 且剛好形成一個(gè)循環(huán)。
他們正好分別屬于3，4，5角形數(shù)中的一個(gè)：(P3,127=8128)(P4,91=8281)(P5,44=2882)
這是唯一一組具有此性質(zhì)的4位數(shù)。
現(xiàn)在要找到也具有1性質(zhì)（首尾形成循環(huán)）的由6個(gè)4位數(shù)形成的一組數(shù)，它們要正好按順序分別屬于3~8角形數(shù)，并求出它們的和。
神奇.
首先稍稍分析一下，因?yàn)橹灰笳?位數(shù)，所以我們可以先獲得3~8角形數(shù)中所有的4位數(shù)，并儲存在6個(gè)數(shù)組中。（可以用P[i][j]儲存，代表i角形數(shù)的第j個(gè)序列的數(shù)）：
total[i]記錄i角形數(shù)的角形數(shù)總數(shù);
思路有很多，可以直接無腦用for暴搜，或者把6個(gè)4位數(shù)拆成12個(gè)部分，直接令它們兩兩相等，再去判斷它們是否是P3~P8，這里僅給出遞歸深搜的寫法；
利用5個(gè)數(shù)組構(gòu)建遞歸深搜DFS的算法：
從三角形數(shù)開始，遍歷每個(gè)三角形數(shù)；
每一次深搜都會在外部用數(shù)組記錄當(dāng)前備選的數(shù)。(findx[]數(shù)組)（61行與73行）
若當(dāng)前遍歷到n角形（8>n>3）（外部的found[]數(shù)組記錄當(dāng)前在深搜哪一角形），會與最新的備選數(shù)（上一個(gè)已選角形數(shù)）匹配（68行至71行）
即滿足前者的后2位與后者的前2位想等即匹配成功，存入備選數(shù)組然后遞歸搜下一個(gè)角形
但這個(gè)深搜是放在循環(huán)中的，即若下一個(gè)角形至最后沒有找到的話，這里會接著向后找能與上一個(gè)角形數(shù)匹配的當(dāng)前角形數(shù)；（70行至77行）
若遍歷到8角形數(shù)時(shí)則會與第一個(gè)備選角形數(shù)（3角形數(shù)）匹配（48至57行）
若匹配成功則直接輸出。
主函數(shù)直接調(diào)用getP()和DFS(3)即可。
6個(gè)數(shù)分別為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個(gè)立方數(shù)（包括本身） ：345^3 384^3 405^3
345的立方是全排列能得到3個(gè)立方數(shù)的最小的立方數(shù)
找到全排列能得到5個(gè)立方數(shù)的最小的立方數(shù)。
不知道具體的上限所以求穩(wěn)姑且先用了大整數(shù)；
在29題的時(shí)候用大整數(shù)乘法寫了個(gè)大整數(shù)簡易的指數(shù)運(yùn)算，用來算3次方剛剛好
29題指路..（對應(yīng)下面的expo函數(shù)）全排列和數(shù)化數(shù)組數(shù)組化數(shù)不多講，為了縮小范圍不妨先跑一遍所有3位數(shù)的3次方，會發(fā)現(xiàn)莫得（這部分自己驗(yàn)證撒） 并且4位數(shù)的一下能找到4個(gè)
所以姑且先將范圍界定在4位數(shù)，先用一個(gè)數(shù)組cube[10000][10000]獲得所有4位數(shù)的3次方并以數(shù)組形式存在cube[n][]里（cube[n][]代表4位數(shù)n的逆序排列）
判斷全排列是否相同可以用另2個(gè)數(shù)組儲存逆序然后都sort排序一下直接比較
在主函數(shù)中調(diào)用getcube()函數(shù)然后用5個(gè)for循環(huán)搜索即可（主函數(shù)較為猙獰 不放了）
大概2min能跑出來（還是比較慢了
5個(gè)4位數(shù)：
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是個(gè)5位數(shù)，同時(shí)也是5次方數(shù)，134217728=8^9是個(gè)9位數(shù)同時(shí)也是9次方數(shù)
有多少個(gè)n位數(shù)同時(shí)也是n次方數(shù)？
這道題可以自己拿計(jì)算機(jī)確定范圍然后數(shù)出答案...
稍稍說下分析：
顯然，如果一個(gè)x位數(shù)（除了1外，1=1^1）能表示成n的x次方，2<=n<=9；
9^21次方還是個(gè)21位數(shù)，9^22以上的x就不是22位數(shù)了。所以對9而言上限是9^21，且從11位數(shù)起，8^11是10位數(shù)，所以從11位數(shù)到21位數(shù)只有9能滿足9^x是x位數(shù)，即11~21位數(shù)只有 11個(gè) 數(shù)字滿足x位數(shù)=n^x；
以此類推可知7從7位數(shù)開始7^x不再為7位數(shù)，即7~10位數(shù)只有8，9能滿足x位數(shù)=n^x，即7~10位數(shù)有4×2= 8個(gè) 數(shù)字滿足；
6從5位數(shù)起...即5~6位數(shù)只有7，8，9...? 有2×3=6個(gè)數(shù)字；
5從4位數(shù)起? ?4位數(shù)只有6，7，8，9? ?有4個(gè)數(shù)字；
4從3位數(shù)起? ?3位數(shù)只有5，6，7，8，9 有5個(gè)數(shù)字；
3從2位數(shù)起? ?2位數(shù)只有4，5，6，7，8，9 有6個(gè)數(shù)字
1位數(shù)有 1~9 9位數(shù)字；
綜上有49個(gè)數(shù)字。
ans：49
（難得白給）
最近不定期隨緣更新.
