UVa@hackコミュのN^x=a,(N+1)^x=b

むーさんです。

とりあえず、Acceptされました。。。。

　まだまだ、解く速度はひどい（＝アルゴリズムがひどい）ですが、１０秒以上かかっていたのが、７秒も短縮されました。
　何を変えたのか。それは。。。。

N^xを計算するのに数学関数powを用いていたのを止め、自分で作成したN^xを計算するプログラムを用いるようにしたこと。。。。

　ここではmath.hに含まれる関数を用いない方がいいということですか。

虱潰しって、具体的にどう計算しました？

＞もっこしさん

書き込み有難う御座います。
powを用いて、その速度。。。
たしかに私のソースは他に見なおすべき所がたくさんあるのかと思います。
検討していくつもりです。ありがとうございます。

＞白猫さん

書き込み有難う御座います。
ソースがあったほうがわかりやすいかも知れませんので、恥を覚悟でソースをのせます。
虱潰しの方法は、N^x=a,(N+1)^x=bをみたすかどうかを、あるNに対してxを変化させていき、見つからなかったらNをインクリメントさせて、同様のことをくり返していくものです。
御指摘を頂ければ非常にうれしいです。よろしくお願いします。
まずは、Time Limit Exceededのものから。

/*-------------------------------------------------*/
#include<stdio.h>
#include<math.h>

int main(void)
{
int a, b; /*Input*/
int N, x;

while(1){
scanf("%d %d",&a,&b);if(a==0 && b==0) exit(1);
/********************N^x=b,(N+1)^x=aを解く。*********************/
N=1;

while(1){
x=0;
while(1){
if(pow(N+1,x)>a || pow(N,x)>b){break;}
if(pow(N+1,x)==a && pow(N,x)==b){goto END;}
x++;
}
N++;
}
/****************************************************************/
END:
if(N==1){
printf("%d %d\n",x,2*a-b);
}
else
{
printf("%d %d\n",(b-1)/(N-1),a*(N+1)-b*N);
}
}

return 0;

}

/*-------------------------------------------------------*/

次にとりあえず、Acceptされたもの。
/*------------------------------------------------------*/
#include<stdio.h>
#include<math.h>

int times(int k,int x);

int main(void)
{
int a, b;
int N, x;

while(1){
scanf("%d %d",&a,&b);if(a==0 && b==0) exit(1);
/********************N^x=b,(N+1)^x=aを解く。*********************/
N=1;

while(1){
x=0;
while(1){
if(times(N+1,x)>a || times(N,x)>b){break;}
if(times(N+1,x)==a && times(N,x)==b){goto END;}
x++;
}
N++;
}
/****************************************************************/
END:
if(N==1){
printf("%d %d\n",x,2*a-b);
}
else
{
printf("%d %d\n",(b-1)/(N-1),a*(N+1)-b*N);
}
}

return 0;

}
/*********kのl乗を計算する関数**********/
int times(int k, int l)
{
int i;
int M;
M=1;
for(i=0;i<l;i++){
M=M*k;
}
return M;
}
/*----------------------------------------------------------*/

追記：
先ほど書きこんだソースですが、mixiに書きこんだら、うまく字下げ等ができていなくて申訳御座いません。
読みずらいですが、お願いします。

>虱潰しの方法は、N^x=a,(N+1)^x=bをみたすかどうかを、あるNに対してxを変化させていき、見つからなかったらNをインクリメントさせて、同様のことをくり返していくものです。

Nからxを定める時、線形に（xを一個ずつ前から見ていく）探索してるが、二分探索を用いると速くなると思う。
二分探索は単純且つ非常に使えるので覚えてると便利。以下wiki から
http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

んで、この方法の計算量を単純に見積もると、Nを与えられる数の小さい方の数とすると、O( N ) の計算量を必要とする（最悪 x が１の場合は N 必要となる）。

逆に、x から N の値を定めることを考える。x の値は大きくても３２。N は二分探索を用いれば logN　で探せる。よって計算量 O( logN )となる。（もっこしさんの方法）

＞白猫さん

御指摘ありがとうございます。
勉強し、試してみます。

＞もっこしさん

＞aとbは既に与えられているから，xかNのどちらかを固定すれば，もう一方は計算で求められますよね？

そうですね。そうかぁ〜。
修行します。
ありがとうございます。