[yukicoder] No.16 累乗の加算

問題

No.16 累乗の加算 - yukicoder

累乗をいかにして求めるかが肝です。

二分累乗法

累乗を求めるアルゴリズムに二分累乗法というものがあります。下記のサイトが参考になりました。これを利用して解答を得ます。

Comp Prog DosC Note 483

augusuto04.hatenablog.com

コード

import java.util.Scanner;

public class Exec0016 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int N = scan.nextInt();
        long []a = new long[N];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();
        int k = 1000003;
        long ans = 0;
        for(int i = 0; i < N; i++) {
            ans += pow(x, a[i], k);
            ans = ans % k;
        }
        System.out.println(ans % k);
    }
    public static long pow(long x, long n, int k) {
        if(n == 0) {
            return 1;
        }
        if(n % 2  == 0) {
            return pow(x * x % k, n / 2, k);
        }else {
            return x * pow(x, n - 1, k) % k;
        }
    }
}