白駿1629乗算

13685 ワード
白駿 テキストリンク
https://www.acmicpc.net/problem/1629


トラブルシューティング


平方の性質と型の性質が分かれば,これは容易に解く問題である.
問題はA,B,Cともに2147483647以下の自然数であり,指数を対分処理し,時間複雑度はO(logn)である.
この場合,指数が偶数と奇数の場合を分けて考えるべきである.次の例です.10^11 = 10^5 * 10^5 * 10 10^5 = 10^2 * 10^2 * 10 10^2 = 10^1 * 10^1つまり、指数が偶数の場合は밑^지수/2 * 밑^지수/2指数が奇数の場合,밑^지수/2 * 밑^지수/2 * 밑の形態であることがわかる.

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * Math 클래스의 pow 메소드를 이용해서 풀려고 했으나 틀림
 * 제곱의 성질을 이용하여 분할정복으로 풀이 -> 시간복잡도 O(logN)
 * 힌트 : 지수를 2로 나눔
 */

public class b1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        System.out.println(func(a, b, c));
    }

    public static long func(long a, long b, long c) {
        // b가 1일 때
        if (b == 1) {
            return a % c;
        }   
        long temp = func(a, b / 2, c);
        // b가 홀수일 때
        if (b % 2 == 1) {
            return (temp * temp % c) * a % c;
        }
        // b가 짝수일 때
        return temp * temp % c;
    }
}

振り返る


最初は時間的複雑さを考慮せず,Mathクラスのpow法を用いて簡単に解いた.連続的な誤りが得られ,二乗の性質とモードの性質に関するヒントが得られ,この問題を解決した.何度も試して成功した!

イニシャルコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        long result = 0;
        result = (long) Math.pow(a, b);
        System.out.println(result%c);
    }
}
centos eth 2をeth 0に変更
プログラマSummer/Winter Coding(~2018)-基地局のインストール