## 2013年10月10日 星期四

### UVa 107 - The Cat in the Hat

Keyword: brute force, math

Algorithm:

Maybe there's a better solution, but I chose this one.
I tried all possible N and check if this N is correct or not.
A number is said to be correct if log( input ) / log( N ) is an integer and the number of working cats is the same as given one.
However, if you want to use log function, take care of precision error.

Code:
```#include<cstdio>
bool ok( int init, int h )
{
while( init % h == 0 )
init /= h;
return init == 1;
}
int lev( int init, int h )
{
int dep = 0;
while( init != 1 )
init /= h, ++dep;
return dep;
}
int pow( int base, int exp )
{
int back = base;
for( int i = 2; i <= exp; ++i )
back *= base;
return back;
}

int main()
{
int N, init, work, level;

while( scanf( "%d %d", &init, &work ) && init+work )
{
for( N = 1; N < init; ++N )
if( ok( init, N+1 ) )
if( pow( N, level = lev( init, N+1 ) ) == work )
break;
int idle = N == 1? level : ( pow( N, level ) - 1 ) / ( N-1 ), h = work + init;
for( int i = level-1; i; --i )
h += init / pow( N+1, i ) * pow( N, i );
if( init != 1 )
printf( "%d %d\n", idle, h );
else//
printf( "%d %d\n", 1-work, 1 );
}

return 0;
}```