学步园

      开始题目看错了...各种坑各种WA...注意根据题意1+k^1+k^2+...k^r...第一个1是可要可不要的...囧....

      两种方法..

     方法一:

      这是参考了别人的思路... 就是r=1,2的特殊判断...r>=3的打表dp[10002][42]....都是用二分查找...

Prrogram:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define oo 2000000000
#define pi acos(-1)
using namespace std;
ll n,r,k,M,d[10005][43];
void getans(ll n)
{
        ll i,L,R,MID;
        L=2;  R=1000005;
        while (R-L>1)
        {
               MID=(L+R)/2;
               if (1+MID+MID*MID>n) R=MID;
                   else L=MID;
        }
        if (1+L+L*L==n && 2*L<r*k) r=2,k=L;
        for (i=3;i<=40;i++)
        {
               L=2;   R=10002;
               while (R-L>1)
               {
                     MID=(R+L)/2;
                     if (d[MID][i]==-1 || d[MID][i]>n) R=MID;
                          else  L=MID;
               }
               if (d[L][i]==n && i*L<r*k) r=i,k=L;
        }
        return;
}
int main()
{ 
        ll i,j;
        M=1;
        for (i=1;i<=12;i++) M*=10;
        memset(d,-1,sizeof(d));
        for (i=2;i<=10000;i++) d[i][3]=1+i+i*i+i*i*i;
        for (i=2;i<=10000;i++)
        {
                k=i*i*i;
                for (j=4;j<=40;j++)
                    if (d[i][j-1]>M) break;
                       else k*=i,d[i][j]=d[i][j-1]+k;
        }
        while (scanf("%lld",&n)!=EOF)
        {
                r=1;   k=n-1;
                getans(n);
                getans(n+1);
                printf("%lld %lld\n",r,k);
        }
        return 0;
}

   方法二:

      自己的思路...开始时题目看错了..各种WA..怀疑算法问题...题目的细节抓住后..重新实现这个算法..AC...

      通过观察发现的..若r,n已经确定..那么k如果存在整数解..则为 n^(1/r)....枚举r..验证k即可...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
#include<set>
#define ll long long
#define oo 2000000000
#define pi acos(-1)
using namespace std;
ll n,r,k,M,d[10005][43];
void getans(ll n)
{
        ll i,h,j,p,x;
        for (i=2;i<=40;i++)
        {
               p=(ll)pow(n,1.0/i);
               h=0;  x=1;
               for (j=0;j<=i;j++) h+=x,x*=p;
               if (h==n && i*p<r*k) r=i,k=p;
        }
        return;
}
int main()
{ 
        while (scanf("%lld",&n)!=EOF)
        {
                r=1;   k=n-1;
                getans(n);
                getans(n+1);
                printf("%lld %lld\n",r,k);
        }
        return 0;
}