首页 > 代码库 > HDU 4282 A very hard mathematic problem

HDU 4282 A very hard mathematic problem

2024-07-04 00:37:05   227人阅读

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4287



Problem Description
　　Haoren is very good at solving mathematic problems. Today he is working a problem like this:
　　Find three positive integers X, Y and Z (X < Y, Z > 1) that holds
　　 X^Z + Y^Z + XYZ = K
　　where K is another given integer.
　　Here the operator “^” means power, e.g., 2^3 = 2 * 2 * 2.
　　Finding a solution is quite easy to Haoren. Now he wants to challenge more: What’s the total number of different solutions?
　　Surprisingly, he is unable to solve this one. It seems that it’s really a very hard mathematic problem.
　　Now, it’s your turn.

Input
　　There are multiple test cases.
　　For each case, there is only one integer K (0 < K < 2^31) in a line.
　　K = 0 implies the end of input.
　　

Output
　　Output the total number of solutions in a line for each test case.

Sample Input
9
53
6
0

Sample Output
1
1
0
　　

Hint

9 = 1^2 + 2^2 + 1 * 2 * 2
53 = 2^3 + 3^3 + 2 * 3 * 3

Source
2012 ACM/ICPC Asia Regional Tianjin Online

Recommend
liuyiding | We have carefully selected several similar problems for you:4267 4268 4269 4270 4271


题意：
给你一个式子x^z + y^z + x*y*z = k，k 为给定的某个int 范围内的数字。
求共有多少组关于x,y,z 的解。（0< x < y,z > 1）
解题思路：
显然当z 越大的时候x,y 的值越小。
由于y 最小等于2，所以有2^z < k，又k < 2^31，所以有z < 31。
1、首先考虑当z=2 的时候，式子左边可以化为(x+y)^2 = k 的形式。
所以当k 是完全平方数的时候，(x,y) 才有可能有解。
假如m^2 = k ，问题就相当于求x+y = m (x < y) 的解的组数。
容易得出ans=(m-1)/2;
2、然后考虑当z>=3 的时候。

枚举就好！


代码如下：

#include<cstdio>
#include<cmath>
#define LL __int64
LL POW(LL x , int z)
{
	LL ans = 1;
	for(int i = 1 ; i <= z ;i++)
	{
		ans*=x;
	}
	return ans;
}
int main()
{
	LL x,y,tx,ty,ans;
	int z,k;
	while(~scanf("%d",&k) && k)
	{
		ans = 0;
		LL tmp = (int)sqrt(k*1.0);
		if(tmp *tmp == k)//若n是一个完全平方数
			ans+=(tmp-1)/2;
		for( z = 3 ; z < 31 ; z++)//z最大为30，开始枚举
		{
			for(LL x = 1 ; ; x++)
			{
				tx = POW(x,z);
				if(tx >= k/2)
					break;
				for(LL y = x+1; ; y++)
				{
					ty = POW(y,z);
					if(tx+ty+x*y*z > k)
						break;
					else if(tx+ty+x*y*z == k)
					{
						ans++;
						break;
					}
				}
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}



联系
我们