Java向け競プロライブラリ(最大公約数・最小公倍数・約数洗い出し)

最大公約数・最小公倍数が絡んでくる問題向けライブラリです

例えば以下の問題で役に立ちます

AtCoder Beginner Contest 162 C - Sum of gcd of Tuples (Easy)

AtCoder Beginner Contest 253 D - FizzBuzz Sum Hard

final class GcdLcmCalculator {

	/**
	 * ユークリッドの互除法を利用して2整数の最大公約数を取得する
	 * @param a 整数
	 * @param b 整数
	 * @return aとbの最大公約数
	 */
	public static final long calculateGcd(long a, long b) {
		if (b == 0) {
			return a;
		}

		return calculateGcd(b, a % b);
	}

	/**
	 * 2整数の最小公倍数を取得する
	 * @param a 整数
	 * @param b 整数
	 * @return aとbの最小公倍数
	 */
	public static final long calculateLcm(long a, long b) {
		return a / calculateGcd(a, b) * b;
	}

}

整数の約数一覧を取得するライブラリです

例えば以下の問題で役に立ちます

AtCoder Beginner Contest 249 D - Index Trio

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

final class DivisorHelper {

	/**
	 * 整数の約数一覧を取得する
	 * @param n 対象の整数
	 * @return nの約数リスト
	 */
	public static final List<Long> getDivisorsOf(long n) {
		Deque<Long> less = new ArrayDeque<Long>();
		Deque<Long> greater = new ArrayDeque<Long>();
		for (long d = 1; d * d <= n; ++d) {
			if (n % d != 0) {
				continue;
			}

			less.addLast(d);

			long q = n / d;
			if (d != q) {
				greater.addLast(q);
			}
		}

		List<Long> res = new ArrayList<Long>();
		while (!less.isEmpty()) {
			res.add(less.pollFirst());
		}

		while (!greater.isEmpty()) {
			res.add(greater.pollLast());
		}
		return res;
	}

}