HDU 4282 A very hard mathematic problem (매 거 + 2 점)

제목 링크 ":
http://acm.hdu.edu.cn/showproblem.php?pid=4282
제목:
방정식 을 정 하 다 :    x^z + y^z + x*y*x = k;
주어진 k 에 대해 서 는 3 원 그룹 이 몇 개 있 습 니까? (x,y,z) 
이 방정식 을 성립 시키다.
그 속   0x, y, z 는 모두 정수 이다.
분석:
현재 문제 의 범위 와 방정식 의 구조 에 따라 각 수의 범 위 를 먼저 예측 할 수 있다.
2<=z<=32 , 1<=x그런 후에 우 리 는 방정식 을 분석 해 보 았 다. 그 중에서 임의의 두 수가 고정 되 었 을 때
이 방정식 의 왼쪽 은 모두 단 조 롭 게 증가 하고 있 기 때문에 우 리 는 그 중의 두 개 를 매 거 할 수 있다.
그리고 2 분 동안 다른 존 재 를 판단 합 니 다. 편 의 를 위해 서. 우 리 는 z, y 를 매 거 할 수 있다.
이분 판단 x.
코드 는 다음 과 같 습 니 다:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;

LL k;

LL quick(LL a,LL b)
{
    LL tmp =1;
    for(int i=0;i<b;i++){
        tmp=tmp*a;
        if(tmp>=k) return -1;
    }
    return tmp;
}

LL calu(LL x,LL y,LL z){
    return quick(x,z)+quick(y,z)+x*y*z;
}
bool bin_search(LL y,LL z){
    LL low = 1,high = y,mid;
    while(low<high){
        mid=(low+high)>>1;
        LL tmp = calu(mid,y,z);
        //cout<<"mid "<<mid<<endl;
        //cout<<"tmp "<<tmp<<endl;
        if(tmp==k) return true;
        else if(tmp<k) low=mid+1;
        else high =mid;
    }
    return false;
}

int main()
{
    while(~scanf("%lld",&k)&&k!=0){
        if(k==1||k==2){
            puts("0");
            continue;
        }
        LL INF = (LL) sqrt(k*1.0);
        LL cnt=0;
        for(LL z = 2;z<=32;z++){
            for(LL y = 2;y<=INF;y++){
                LL tmp = quick(y,z);
                if(tmp == -1) break;
                if(bin_search(y,z))
                    cnt++;
            }
        }
        printf("%I64d
",cnt); } return 0; }



좋은 웹페이지 즐겨찾기