题目链接:Click here~~
题意:
给你一个式子 x^z + y^z + x*y*z = k,k 为给定的某个 int 范围内的数字。
求共有多少组关于 x,y,z 的解。(0< x < y,z > 1)
解题思路:
这题纠结了2天,我擦。今天终于把错误拍出来了。
观察式子不难发现,显然当 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) 的解的组数。
容易得出,当m为偶数时,解组数为 m/2-1;当m为奇数时,解组数为 (m-1)/2。
2、然后考虑当 z>=3 的时候。
当 z=3 的时候,x,y 可能取到的值最大,而稍加计算可以得出 y 的最大值是1290.xx,设这个值为M。
那么枚举x,z的复杂度变为O(M*30),大概是O(10^4)。
如果再直接枚举y的话,复杂度为O(M^2 *30),大概是O(10^7),略大。(不过也能140MS AC)。
那么有没有好的方法呢?
显然当 x,z 确定后,式子关于 y 是单调递增的,于是可以二分,将复杂度降为O(M*logM*30),大概是O(10^5)。(15MS AC)。
第一次用小号交的,爆了0MS,然后竟然排到了rank1。O(∩_∩)O...
Ps:思路一直都是对的,可是昨天WA了一天。
这种题要注意一些细节。在二分的时候,我 y 的右边界一直取的是当 z = 3的时候的 M。这种贪方便的做法会引发一个问题。
就是当 z 逐渐变大的时候,二分区间中很多的值会溢出long long 的范围,导致判断大小错误。
幸好值溢出时会变负,所以我们可以根据值是否为负来判断是否溢出。若溢出,直接等效于大于。
#include <stdio.h>
#include <math.h>
typedef __int64 LL;
int k,x,y,z;
LL xz,yz;
LL myPow(int a,int n)
{
LL ans = a;
while(--n)
ans *= a;
return ans;
}
LL fun(int Y)
{
return xz + yz + x*Y*z;
}
bool FindIt(int l,int r)
{
while(l <= r)
{
int mid = (l+r)/2;
yz = myPow(mid,z);
LL f = fun(mid);
if(f == k)
return true;
if(f<0 || f>k)
r = mid-1;
else
l = mid+1;
}
return false;
}
int main()
{
while(scanf("%d",&k),k)
{
int ans = 0;
int sq = sqrt(k*1.0);
if(sq*sq == k)
ans += (sq-1)/2;
for(z=3;z<31;z++)
{
for(x=1;;x++)
{
xz = myPow(x,z);
if(xz >= k/2)
break;
if(FindIt(x+1,1300))
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
HDU 1022 Train Problem I 附详细思路
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-确定比赛名次(HDU-1285).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
hdu_2102_passed_sorce
The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
杭电ACMhdu1163
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
HDU的一题........HDU DP动态规