# Project Euler 03

### OVERVIEW

• Project Euler 03
• 1.E22：Name score
• 2.E32：Pandigital products
• 3.E33：Digit cancelling fractions
• 4.E36：Double-base palindromes
• 5.E30：Digit fifth powers
• 6.onlineJ599：两数之和
• （1）暴力法：
• （2）二分法：
• （3）双指针法：
• （4）哈希表：
• （5）问题总结：
• 7.onlineJ600：杨氏矩阵
• （1）暴力法：
• （2）值比较法：

#### 1.E22：Name score

Using names.txt , a 46K text file containing over five-thousand first names,

begin by sorting it into alphabetical order.Then working out the alphabetical value for each name,

multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN,

which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list.

So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

1. 将name.txt文件下载下来，进行初步处理`%s/","/ /g`（将连接符替换为空格分隔）、`%s/"/ /g`（处理开头结尾的单引号）
2. 将名字输入保存到name[6005]数组中
3. 首先使用sort算法对name数组进行排序
4. 外循环遍历name数字中的每一个名字，内循环遍历name的每一个字母计算每个名字的价值value
5. 输出最后累加的score分数
``````#include
#include
#include
using namespace std;

string name[6005];
int n;

int main(){
while(cin >> name[n]){
n++;
}
sort(name, name + n);
long long score = 0;
for(int i = 0; i < n; ++i){
int value = 0;//name的价值
for(int j = 0; j < name[i].size(); ++j){
value += name[i][j] - 'A' + 1;
}
score += value * (i + 1);
}
cout << score << endl;
return 0;
}
``````

#### 2.E32：Pandigital products

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once

For example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254,

containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

7254是一个特殊的乘积，因为在等式39 × 186 = 7254中，被乘数、乘数和乘积恰好是1至9全数字的。

1. 枚举的范围：

外层for循环范围，至少应从2开始（若为1乘数与成积重复必不为全数字），至多到98结束（3位数乘积将达到6位数必不符合）

内层for循环范围，应该从`j=i+1`开始（乘数与被乘数重复），可暂时设置为死循环（在循环体中当`i``j``i*j`位数和大于9结束）

2. 对于全数字的判断

开辟一个`mark[10]`标记数组，将被判断的数字拆分存入标记数组中，查看当遍历结束时标记数组中是否全为1（如果满足则`+=ans`

3. 对于乘积相同的等式重复判断

开辟一个`check[10005]`标记数组，如果乘积第1次出现则计入累加，否则乘积重复不记入

``````#include
#include
using namespace std;

//1.求数字位数
int digit(int x){
return floor(log10(x)) + 1;
}

//2.检验每一位数字是否重复
int work(int *mark, int num){
while(num){
int temp = num % 10;//取num的最后一位
if(mark[temp] == 1){
return 0;//如果数字曾经出现过则直接return 0
}
mark[temp] = 1;//数字没有出现过将其标记值设为1
num /= 10;
}
return 1;
}

//3.检查数字是否为全数字
int func(int x, int y, int z){
int mark[10] = {0};//mark为标记数组，用于检查数字是否重复
if(work(mark, x) && work(mark, y) && work(mark, z) && mark[0] == 0){
return 1;//如果3个数字都不冲突,且数字当中没有0则返回1
}
return 0;
}

int main(){
int ans = 0, check[10005] = {0};
for(int i = 2; i < 99; ++i){
for(int j = i + 1; 1; ++j){
int a = digit(i), b = digit(j), c = digit(i * j);
if(a + b + c > 9){
//1.a+b+c>9不可能是答案直接退出循环
break;
}
if(a + b + c == 9){
//2.a+b+c==9对数字进行进一步验证
if(func(i, j, i * j)){
//利用func检查是否符合全数字
cout << i << " " << j << " = " << i * j << endl;
if(check[i * j] == 0){
//利用check进行重复检查
check[i * j] = 1;
ans += i * j;
}
}
}
}
}
cout << ans << endl;
return 0;
}
``````

#### 3.E33：Digit cancelling fractions

The fraction 49/98 is a curious fraction,

as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8,

which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction,

less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

49/98是一个有趣的分数，缺乏经验的数学家可能在约简时错误地认为等式49/98 = 4/8

1. 枚举范围：外层for循环范围11~99，内层for循环范围`i+1`-99
2. 对于非凡解的判定：将约去同一数字后的分数与约去前的分数交叉相乘，若相等则为非凡解（对于平凡解的去除，任一数字不为0）
``````#include
using namespace std;

//1.判断分数是否为不平凡解
int func(int x, int y){
int x1 = x / 10, x2 = x % 10, y1 = y / 10, y2 = y % 10;//将两位数进行拆解
if(!x1 || !x2 || !y1 || !y2){
return 0;//如果数字中含有0则一定为平凡解return 0
}
if(x1 == y1 && x * y2 == y * x2) return 1;
if(x1 == y2 && x * y1 == y * x2) return 1;
if(x2 == y1 && x * y2 == y * x1) return 1;
if(x2 == y2 && x * y1 == y * x1) return 1;
return 0;
}

//2.辗转相除求a与b的最大公约数
int gcd(int a, int b){
if(b == 0){
return a;
}
return gcd(b, a % b);
}

int main(){
int a = 1, b = 1;
for(int i = 11; i < 100; ++i){
for(int j = i + 1; j < 100; ++j){
if(func(i, j)){
//如果j\i为不平凡的解，则打印例子
cout << i << " / " << j << endl;
a *= i;
b *= j;
}
}
}
int temp = gcd(a, b);//temp为a与b的最大公约数
a /= temp;
b /= temp;
cout << a << " / " << b << endl;
return 0;
}
``````

#### 4.E36：Double-base palindromes

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

（请注意无论在哪种进制下，回文数均不考虑前导零。）

``````#include
using namespace std;

//判断是否为回文数
int func(int num, int x){
int raw = num;
int temp = 0;//最后的temp值为回文数
while(num){
temp = temp * x + num % x;
num /= x;
}
return temp == raw;
}

int main(){
int ans = 0;
for(int i = 1; i < 1000000; ++i){
if(func(i, 10) && func(i, 2)){
cout << i << endl;
ans += i;
}
}
cout << ans << endl;
return 0;
}
``````

#### 5.E30：Digit fifth powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

1. 枚举范围如何确定？

首先考虑时间效率优化，对于`1-9`的五次幂可以先计算存储到一个数组中（避免每次重复计算，提升时间效率）

利用关系（该数字 = 其各位数字的五次幂之和）确定枚举范围，

假设该数字的位数为n，则有该数字取值为[1-10n)，五次幂之和的取值范围为[n * 05, n * 9n]

故另10n = n * 9n则可以解出该数字位数n的最大值，从而确定枚举范围（n的取值大致为5~6之间，枚举范围取6

2. 符合要求答案的条件：各位数字的五次幂之和等于该数字，则符合题目条件进行累加

``````#include
using namespace std;

int penta[15];

void init(){
for(int i = 1; i < 10; ++i){
int temp = 1;
for(int j = 0; j < 5; ++j){
temp *= i;
}
penta[i] = temp;
cout << i << ":" << penta[i] << " " << endl;
}
}

int func(int num){
int raw = num;
int temp = 0;
while(num){
temp += penta[num % 10];
num /= 10;
}
return temp == raw;
}

int main(){
init();
int ans = 0;
for(int i = 2; i < 1000000; ++i){
if(func(i)){
ans += i;
cout << i << endl;
}
}
cout << ans << endl;
return 0;
}
``````

``````int penta[15];
void init(){
for(int i = 1; i < 10; ++i){
int temp = 1;
for(int j = 0; j < 5; ++j){
temp *= i;
}
penta[i] = temp;
cout << i << ":" << penta[i] << " " << endl;
}
}
//与回文数字判断代码相似
int func(int num){
int raw = num;
int temp = 0;
while(num){
temp += penta[num % 10];
num /= 10;
}
return temp == raw;
}
``````

#### 6.onlineJ599：两数之和

``````6 15
1 5 6 7 10 26
``````
``````1 4
``````
##### （1）暴力法：
``````#include
#include
using namespace std;

int num[1000005];
int n, target;

int main() {
scanf("%d%d", &n, &target);
for (int i = 0; i < n; ++i) {
scanf("%d", &num[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (num[i] + num[j] == target) {
cout << i << " " << j << endl;
return 0;
}
}
}
cout << "not fimd" << endl;
return 0;
}
``````

##### （2）二分法：

1. 使用for循环遍历数组中的每一个数字
2. 在循环体内部，使用target值减去当前遍历的数字值（结果为配对值），在数组中二分查找该数字
3. 如果找到配对值则输入答案，否则没有配对值输出nofind

``````#include
#include
using namespace std;

int num[1000005];
int n, target;

int main(){
scanf("%d%d", &n, &target);
for(int i = 0; i < n; ++i){
scanf("%d", &num[i]);
}
for(int i = 0; i < n; ++i){
int temp = target - num[i];
int l = i + 1, r = n - 1;
while(l <= r){
int mid = (l + r) / 2;
if(temp == num[mid]){
cout << i << " " << mid << endl;
return 0;
}
if(temp < num[mid]){
r = mid - 1;
}else{
l = mid + 1;
}
}
}
cout << "not fimd" << endl;
return 0;
}
``````
##### （3）双指针法：

1. 分别初始化两个指针，指向数组的起始和结尾
2. 将数组头尾元素相加sum值与target值比较：
如果sum>target（数据偏大），则将右指针向左移动一位
如果sum 如果sum==target（找到结果），直接输出左右指针
3. 左右指针错开时，target查找结束（数组遍历完成没有找到结果nofind）

``````#include
#include
using namespace std;

int num[1000005];
int n, target;

int main(){
scanf("%d%d", &n, &target);
for(int i = 0; i < n; ++i){
scanf("%d", &num[i]);
}
int l = 0, r = n - 1;
while(l < r){
int t = num[l] + num[r];
if(t == target){
printf("%d %d\n", l, r);
return 0;
}
if(t > target){
r--;
}else{
l++;
}
}
printf("no find\n");
return 0;
}
``````
##### （4）哈希表：
``````#include
using namespace std;

int n, target;
int num[1000005], mark[1000005];

int main() {
scanf("%d%d", &n, &target);
for (int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
mark[num[i]] = i;
}
for (int i = 1; i <= n; ++i) {
int temp = target - num[i];
if (mark[temp] != 0) {
printf("%d %d\n", i - 1, mark[temp] - 1);
return 0;
}
}
printf("no find!\n");
return 0;
}
``````

#### 7.onlineJ600：杨氏矩阵

``````3 4
1 2 3 4
5 6 15 20
7 10 20 25
15
``````
``````2 3
``````
##### （1）暴力法：

``````#include
using namespace std;

int n, m, target;
int num[3005][3005];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &num[i][j]);
}
}
scanf("%d", &target);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (num[i][j] == target) {
printf("%d %d\n", i, j);
return 0;
}
}
}
printf("no find!\n");
return 0;
}
``````

##### （2）值比较法：

1. 从矩阵的左下角or右上角出发，进行对target值的依次比较（以从左下角出发为例）
2. 如果target值比当前位置的数值大，则向右移动一格（行具有递增性）
3. 如果target值比当前位置的数值小，则向上移动一格（列具有递减性）
4. 经过多次移动后，当最后值等于target值时，输出行、列的下标

``````#include
using namespace std;

int n, m, target;
int num[3005][3005];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &num[i][j]);
}
}
scanf("%d", &target);
int x = n, y = 1;//从左下角开始比较
while (x > 0 && y <= m) {
int cur = num[x][y];
if (cur == target) {
printf("%d %d\n", x, y);
return 0;
}
if (cur > target) {
--x;
} else {
++y;
}
}
printf("no find!\n");
return 0;
}
``````