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

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

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

感想

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