首页 > 代码库 > HDU 4282 A very hard mathematic problem --枚举+二分(或不加)
HDU 4282 A very hard mathematic problem --枚举+二分(或不加)
题意：问方程X^Z + Y^Z + XYZ = K (X<Y,Z>1)有多少个正整数解 (K<2^31)
解法：看K不大，而且不难看出 Z<=30, X<=sqrt(K), 可以枚举X和Z，然后二分找Y，这样的话不把pow函数用数组存起来的话好像会T，可以先预处理出1~47000的2~30次幂，这样就不会T了。
但是还可以简化，当Z=2时，X^2+Y^2+2XY = (X+Y)^2 = K， 可以特判下Z= 2的情况，即判断K是否为平方数，然后Z就可以从3开始了，这样的话X^3+... = K的话，X就变为大概1000多了，大大减小了枚举的复杂度，这样的话，直接爆都不会T了，也可以二分，幂函数直接暴力都没事了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 200007lll k;int main(){ lll x,y,z; while(scanf("%I64d",&k)!=EOF && k) { lll kk = (lll)sqrt(1.0*k); lll cnt = 0; if(kk*kk == k) cnt += (kk-1LL)/2LL; lll gen = 2000LL; for(z=3;z<=30;z++) { for(x=1;x<=gen;x++) { lll xz = x; for(ll f=1;f<z;f++) { xz = xz*x; if(xz > k) { xz = k+1LL; break; } } if(xz > k) break; lll low = x+1LL; lll high = gen; while(low<=high) { y = (low+high)/2LL; lll yz = y; for(ll f=1;f<z;f++) { yz = yz*y; if(yz > k) { yz = k+1LL; break; } } if(xz+yz+x*y*z == k) { cnt++; break; } else if(xz+yz+x*y*z > k) high = y-1LL; else low = y+1LL; } } } cout<<cnt<<endl; } return 0;}
HDU 4282 A very hard mathematic problem --枚举+二分(或不加)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。