Project_Euler-29 题解

题目

思路

如果暴力破解的话会有一个问题，那就是数值过大的问题，那我们就需要通过对数据结构来进行操作，这样的话会让代码变得很臃肿。

优化思路

其实，对于一个数值，我们并不需要要将其计算出结果，只需要将它们表示为二元组的形式就可以，而且可以去重，例如：

$4^2=2^4=(2,4)$
$6^4=36^2=(6,4)$
…

我们让其

给定一个数 $x$ ，假设我们想求出最小的满足其 $k$ 次幂等于 $x$ 的值 $y$，即：
$x=y^k$
我们可以这样做：

从2开始遍历，对于遍历到的每一个值$j$，我们尝试对其进行平方运算，并记录平方的次数$k$，截止条件是得出的值小于$x$，其间，如果发现得到一个等于$x$的数，说明存在，这个时候返回$j$，并将次数$k$保存下来。

这样就得到了一个二元组。

优化代码

由于暴力破解的代码太臃肿了，因此作者没写出暴力的代码，这里之间放出优化代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#define MAX_N 100
#define MAX_M 10000typedef struct ppower {int base;int power;
} PP;PP prime_powers;int arr[MAX_M][MAX_M];int prime[MAX_N + 5];
void init() {prime_powers.base = 1;prime_powers.power = 1;for (int i = 2; i <= MAX_N; i++) {if (!prime[i]) prime[++prime[0]] = i;for (int j = 1; j <= prime[0]; j++) {if (i * prime[j] > MAX_N) break;prime[i * prime[j]] = 1;if (i % prime[j] == 0) break;}}
}// 得到最小底数和其对应幂数的代码
int get_base(int x) {for (int i = 2; i <= MAX_N && i < x; i++) {int ans = 1;int temp = i;while (temp < x) {temp *= i;ans++;if (temp == x) {prime_powers.base = i;prime_powers.power = ans;return i;}}}prime_powers.base = x;prime_powers.power = 1;return x;
}// 我们没有采用返回结构体的方式，而是定义了一个全局结构体来保存结果
// 这个函数的作用就是返回上一次求底数对应的幂数
int get_power(int x) {if (x == prime_powers.base) return prime_powers.power;else -1;
}int main() {int ans = 0;init();for (int i = 1; i <= 100; i++) {int base = get_base(i);int power = get_power(pr);printf("i: %d -> base = %d, power = %d\n", i, base, power);}for (int i = 2; i <= MAX_N; i++) {// base是底数int base = get_base(i);// power是幂数int power = get_power(base);for (int j = 2; j <= MAX_N; j++){if (arr[base][power * j]) {continue;} else {arr[base][power * j] = 1;ans++;}}}printf("ans = %d\n", ans);return 0;
}