[Aizu Online Judge] Number Theory

問題

整数に関する問題のセットです。問題の中には今後、ライブラリ的に使うことがあると思います。

http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=NTL

NTL_1_A: Prime Factorize

素因数分解ですね。

コード

import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.close();
        System.out.print(n +":");
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                while(n % i == 0) {
                    System.out.print(" " + i);
                    n = n / i;
                }
            }
        }
        if(n != 1) {
            System.out.print(" " + n);
        }
        System.out.println();
    }
}

NTL_1_B: Power

繰り返し二乗法です。前にもやっとことがありました。

コード

import java.util.Scanner;

public class ProblemB {
    static long MOD = 1000000007;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long m = scan.nextInt();
        long n = scan.nextInt();
        scan.close();
        long ans = modPow(m, n);
        System.out.println(ans);
    }
    static long modPow(long x, long n) {
        long res = 1;
        while(n > 0) {
            if(n % 2 == 1) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            n = n / 2;
        }
        return res;
    }
}

NTL_1_C: Least Common Multiple

最小倍数をもとめる問題です。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[]a = new int[n];
        int p = 1;
        for(int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();

        for(int i = 0; i < n; i++) {
            p = lcm(p, a[i]);
        }
        System.out.println(p);
    }
    static int gcd(int n, int m) {
        if(n > m) {
            return gcd(m, n);
        }
        int k = m % n;
        if(k == 0) {
            return n;
        }else {
            return gcd(n, k);
        }
    }
    static int lcm(int n, int m) {
        return n * m / gcd(n, m);
    }
}

NTL_1_D: Euler's Phi Function

mathtrain.jp

上記のサイトの式を実装しました。

コード

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ProblemD {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        scan.close();
        long t = n;
        List<Long> list = new ArrayList<Long>();
        for(long i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                list.add(i);
                while(n % i == 0) {
                    n = n / i;
                }
            }
        }
        if(n != 1) {
            list.add(n);
        }
        long k = 1;
        for(long i : list) {
            k *= (i - 1);
            t /= i;
        }
        System.out.println(k * t);
    }
}

NTL_1_E: Extended Euclid Algorithm

拡張ユークリッド互除法ですね。逆元を求めようと思い、調べたアルゴリズムです。

コード

import java.util.Scanner;

public class ProblemE {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong();
        long b = scan.nextLong();
        scan.close();
        long[]ans = extendedGCD(a, b);
        System.out.println(ans[0] + " " + ans[1]);
    }
    // as + bt = gcd(a, b)
    static long[] extendedGCD(long a, long b) {
        long s = 0, old_s = 1;
        long t = 1, old_t = 0;
        long r = b, old_r = a;
        while(r != 0) {
            long q = old_r / r;
            long old_s0 = old_s, old_t0 = old_t, old_r0 = old_r;
            old_s = s;
            s = old_s0 - q * s;
            old_t = t;
            t = old_t0 - q * t;
            old_r = r;
            r = old_r0 - q * r;
        }
        return new long[] {old_s, old_t};
    }
}

感想

似たような問題を解いたことがあったので、比較的簡単でした。