When I have seen first the constraint on this problem I've immediately thought that this high value can't be iin the input set OR the problem setter developed a brandly new algorithm not known before. I say this because I've written a fast code for a similar problem that decides if a number is a perfect power or not in gmp (obviously this is an easier problem), that might be in a future gmp version. For one million digits numbers that is hard, so not a perfect power and hasn't got a small prime divisor it runs in 1-5 second.
By asserting the input it is known that the biggest number in the input has got *only* 150000-160000 digits, all of them are perfect powers (so for the solution b>1), and 8 of the input test has got a prime factor<1024. So the input is *weak*. Just for a comparison my code runs in 0.2-0.6 sec. for a hard 150000 digits number.
My pc used for above tests is an amd 2.4 GHz.
I know that for not perfect powers an easy printf("%s 1\n",word); would give in a very easy way point(s) on the contest. But in the other way it is possible that a 10/10 code is unable to detect non perfect powers.
By asserting the input it is known that the biggest number in the input has got *only* 150000-160000 digits, all of them are perfect powers (so for the solution b>1), and 8 of the input test has got a prime factor<1024. So the input is *weak*. Just for a comparison my code runs in 0.2-0.6 sec. for a hard 150000 digits number.
My pc used for above tests is an amd 2.4 GHz.
I know that for not perfect powers an easy printf("%s 1\n",word); would give in a very easy way point(s) on the contest. But in the other way it is possible that a 10/10 code is unable to detect non perfect powers.