🔗 Problem #1009

Jaeyong owns 10 state-of-the-art computers. One day, Jaeyong had a lot of data to process, so he assigned each computer a number from 1 to 10, and decided that the 10 computers would process the data in the following way.

Data #1 goes to computer #1, data #2 to computer #2, data #3 to computer #3, and so on...

Data #10 goes to computer #10, data #11 goes to computer #1, data #12 goes to computer #2, and so on...

The total number of data items is always given in the form $a^b$. Jaeyong suddenly became curious about the number of the computer that would process the last piece of data. Write a program that computes this.

The first line of the input gives the number of test cases $T$. From the next line, each test case gives integers $a$ and $b$. $(1 ≤ a < 100, 1 ≤ b < 1,000,000)$

For each test case, print the number of the computer that processes the last piece of data.

• Input

TC
5
1 6
3 7
6 2
7 100
9 635

• Output

TC
1
7
6
1
9

The answer is right there in the problem. Computers #1 through #10 process the data, and we need to return the number of the computer that processes the very last piece of data.

Suppose there are 12 pieces of data.

The above table makes the pattern easy to spot. The number of the computer processing the data matches the ones digit value of the data number.

That is, the 789235th piece of data is processed by computer #5, because the ones digit of 789235 is 5.

Therefore, we need to extract the ones digit from the given data number. Conveniently, the number of computers is fixed at 10. Since dividing the data number by 10 leaves the ones digit as the remainder, we can use that.

That is, we can use $a^b \% 10$.

However, there are a few things to watch out for. First, if the value of $a^b$ grows too large, it will also affect computational performance. Even before that, if the value gets too large, some rounding error can also occur.

Since we only need the ones digit anyway, we can cleverly work around this.

The table above shows successive powers of 7 to the third power. Since we only need the ones digit, we don't necessarily need to compute the whole thing — we can compute based on just the ones digit. Looking at the formula below makes it even clearer.

$$\text{Ones digit of } 7^3 = 49 * 7 \, \% \, 10 = 3$$ $$\text{Ones digit of } 7^3 = (49 \, \% \, 10) * 7 \% 10 = 9 * 7 \, \% \, 10 = 3$$

Notice that instead of multiplying by 7 starting from 49, we're only taking the ones digit — 9 — and multiplying with that. As in the second formula, the method of calculating with only the ones digit can reduce computational overhead.

Second, there's the handling of computer #10. For example, the calculation for the 30th piece of data would be $30 \, \% \, 10 = 0$. If the result of the calculation is 0, it must be substituted with 10.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Baekjoon problem #1009 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1009">1009 solution</a>
 * @since 2021.06.09 Tue 11:06:38
 */
public class Main
{
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 *
	 * @throws IOException data input/output exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			int a = Integer.parseInt(temp[0]);
			int b = Integer.parseInt(temp[1]);
			
			int result = 1;
			
			for (int j = 1; j <= b; j++)
			{
				result = result * a % 10;
			}
			
			// Treat 0 as 10
			result = result == 0 ? 10 : result;
			
			System.out.println(result);
		}
		
		reader.close();
	}
}

• Math
• Implementation