# UVa 10622

Theory Difficulty:

```   The difficulty level of this problem is really easy irrespective of all .
Beginers can find this problem very helpful to get start with .
```

Coding Difficulty:

```    Any one can get easiness at the time of coding beacause coding level is also easy .
```

Algorithms Used:

```    The knowledge of number theory helps one to solve the problem although it is not must .
```

Good concept on math can help coders at this type of problem .

Solution Description:

```     Given that the square root of 2^31 is less than 47,000, there must not be more than
```

47,000 (positive) inputs that return "2" as their answer. In the same way, the cubic root

```of 2^31 is less than 1300, there are no more than 1300 (positive) inputs that return "3".
```

Given that the vast majority of inputs will return "1", you can just pregenerate all of the answers that won't return "1", store them in a hash map, and output them when necessary.

Don't forget: input numbers can be negative too. Problem Solution Submitted By:

```      I tried best to make the solution of problem simple . But if you can feel any problem
```

then you can let me know .

```                 Imtiaz Ahmed
CSE , 3-1 Dhaka University
```