山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[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;
        }
    }
}