Project Euler 33 Digit cancelling fractions

题意：49/98是一个有趣的分数，因为可能在化简时错误地认为，等式49/98 = 4/8之所以成立，是因为在分数线上下同时抹除了9的缘故。分子分母是两位数且分子小于分母的这种有趣的分数有4个，将这四个分数的乘积写成最简分数，求此时分母的值。

思路：直接枚举判断即可，需要注意 11/22 这种类型的数

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

    > File Name: euler033.c

    > Author:    WArobot

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

    > Created Time: 2017年06月25日 星期日 16时44分46秒

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

#include <stdio.h>

#include <inttypes.h>

int64_t gcd(int64_t a , int64_t b) {

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

}

bool check(int64_t x , int64_t y) {

	int64_t d = gcd(x , y);

	if( (x % 10) == (x / 10) || (y % 10) == (y / 10) )	return false;

	return (((x / d) * (y % 10)) == ((y / d) * (x / 10))) && ((x % 10) == (y / 10));

}

int32_t main() {

	int64_t mol = 1 , den = 1;

	for(int32_t i = 10 ; i < 99 ; i++){

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

			if( check(i , j) ) {

				printf("i = %d , j = %d\n",i,j);

				mol *= (int64_t)i;	den *= (int64_t)j;

			}

		}

	}

	printf("%"PRId64"\n", den / gcd(mol , den));

	return 0;

}

巴特西

Project Euler 33 Digit cancelling fractions

最新文章

热门文章