Project Euler 39 Integer right triangles（素勾股数）

题意：若三边长 { a , b , c } 均为整数的直角三角形周长为 p ，当 p = 120 时，恰好存在三个不同的解：{ 20 , 48 , 52 } , { 24 , 45 , 51 } , { 30 , 40 , 50 }

在所有的p ≤ 1000中，p取何值时有解的数目最多？

思路：可以构建素勾股数，每构建成功一组素勾股数就用其生成其他勾股数，最后扫描一遍取最大值即可。

素勾股数性质：

/*************************************************************************

    > File Name: euler039.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月29日 星期四 00时19分08秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#define MAX_RANGE 1000

int32_t many[MAX_RANGE + 10] = {0};

int32_t gcd(int32_t a , int32_t b) {

	return b == 0 ? a : gcd(b , b % a);

}

void addMany(int32_t a , int32_t b , int32_t c) {

	int32_t p = a + b + c;

	for (int32_t k = p ; k <= MAX_RANGE ; k += p) {

		many[k] += 1;

	}

}

int32_t main() {

	int32_t a , b , c , p;

	for (int32_t i = 2 ; i * i < MAX_RANGE ; i++) {	// 总感觉不思考就暴力的写上上界实在是！太蠢了！

		for (int32_t j = 1 ; j < i ; j++) {

			if (gcd(i , j) != 1)	continue;

			a = 2 * i * j;

			b = i * i - j * j;

			c = j * j + i * i;

			p = a + b + c;

			if (p > MAX_RANGE)		continue;

			addMany(a , b , c);

		}

	}

	int32_t maxMany = 0 , ans = 0;

	for (int32_t i = 1 ; i <= MAX_RANGE ; i++) {

		if (maxMany < many[i]) {

			maxMany = many[i] ,	ans = i;

		}

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

Project Euler 39 Integer right triangles（素勾股数）

最新文章

热门文章

巴特西

Project Euler 39 Integer right triangles（ 素勾股数 ）

最新文章

热门文章

Project Euler 39 Integer right triangles（素勾股数）