[C/C++] #1009 Fixing Distributed Processing,

Efficient Problem Solving in Distributed Processing: Using Number Theory

When it comes to solving distributed processing problems, it is possible to solve them through brute force. However, for more efficient execution, number theory comes into play.

 

distributed processing

The problem itself isn't hard to understand. Imagine you have N data points, and 10 computers sequentially process each data point one by one. The question is: which computer will handle the last data point?

Here is the link to the problem:

[https://www.acmicpc.net/problem/1009](https://www.acmicpc.net/problem/1009)

The given number N is defined by two numbers, \(a\) and \(b\), where \(N = a^b\). The base \(a\) can be as large as 100, and the exponent \(b\) can be as large as 1,000,000. While it’s relatively simple to perform modulus operations on the base, handling the exponent with modular arithmetic exceeds the scope of middle school mathematics.

Nevertheless, since the numbers are not exceedingly large, we can attempt to calculate \(a^b \mod 10\). Let's take \(a = 3\) and \(b = 7\) as an example:

\[
3^1 = 3 \mod 10
\]
\[
3^2 = 9 \mod 10
\]
\[
3^3 = 7 \mod 10
\]
\[
3^4 = 1 \mod 10
\]
\[
3^5 = 3 \mod 10
\]
\[
3^6 = 9 \mod 10
\]
\[
3^7 = 7 \mod 10
\]

From these calculations, you can observe a repeating cycle. Now, let's try \(a = 2\) and \(b = 5\):

\[
2^1 = 2 \mod 10
\]
\[
2^2 = 4 \mod 10
\]
\[
2^3 = 8 \mod 10
\]
\[
2^4 = 6 \mod 10
\]
\[
2^5 = 2 \mod 10
\]

After performing these two calculations, we see that \(a^5 = a^1 \mod 10\). This result hints at a cycle, though we can't be certain just yet. While it’s impractical to try this for every possible \(a\), we can confirm this behavior by running a simple program.

Since \(a^b \mod 10 = (a \mod 10)^b \mod 10\), we only need to calculate values of \(a\) from 1 to 10. By recording the maximum cycle length for each value, we can determine whether a cycle exists.

If you’ve studied a bit of number theory, you might know that Euler's Totient Function \(\varphi(n)\) can help solve this. In my case, I used Euler’s Totient to calculate the cycles. Since 10 factors into \(2 \times 5\), we can compute \(\varphi(10) = 4\). This periodicity of 4 allows us to simplify the calculation:

\[
a^b = (a \mod 10)^{b \mod 4} \mod 10
\]

Using this approach, the problem can be solved efficiently.

//----------------------------------------------------------------------------------
//    baekjoon #1009
//        - by Aubrey Choi
//        - created at 2019-09-08
//----------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    int t, a, b, c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d", &a, &b); c=1; a%=10; b=(b+3)%4+1;
        while(b--) c*=a;
        printf("%d\n", (c+9)%10+1);
    }
    return 0;
}