ANX01 - CodeChef

Hàm f(N) được định nghĩa như sau:

• Gọi S là tổng số chữ số của N.
• Nếu số chữ số của S là một thì F(N) = S.
• Nếu số chữ số của S khác một thì F(A) = F(S) 

Tính F(A^N) với A, N ≤ 10^18.

Hàm F(N) có thể tính nhanh như sau: 

• F(N) = 9, nếu N chia hết cho 9.
• F(N) = N mod 9, trong trường hợp ngược lại.

Sau bao nhiêu năm cũng hiểu được tại sao có được tính chất này. Giờ ta xét N = 1998.
Ta có:
       N = 1999 = 1000 * 1 + 100 * 9 + 10 * 9 + 8 = (999 + 1) * 1 + (99 + 1) * 9 + (9 + 1) * 9 + 8
          = 999 * 1 + 99 * 9 + 9 * 9 + (1 + 9 + 9 + 8)
Cứ thế tiếp tục phân tích tương tự với tổng trong dấu ngoặc ta được giá trị hàm f(N). 
Để đơn giản ta quy ước F(N) = 0 trong trường hợp 9 | N.
Ta có:
      f(ab) = (a * b) % 9 = ((a % 9) * (b % 9)) % 9 = (f(a) * f(b)) % 9.
Từ đó suy ra f(A ^ N) = A ^ N mod 9. 
Dùng lũy thừa nhanh ta có thể qua được hết các subtask.