ヽ｜∵｜ゝ(Fantom) の 開発blog？

import java.lang.reflect.Array;

//１次元配列を生成する
@SuppressWarnings("unchecked")
public static final <T> T[] newArray(final int length, final T[] type) {
    return (T[]) Array.newInstance(type.getClass().getComponentType(), length);
}

//２次元配列を生成する
@SuppressWarnings("unchecked")
public static final <T> T[][] newArray(final int y, final int x, final T[] type) {
    return (T[][]) Array.newInstance(type.getClass().getComponentType(), y, x);
}

//３次元配列を生成する
@SuppressWarnings("unchecked")
public static final <T> T[][][] newArray(final int z, final int y, final int x, final T[] type) {
    return (T[][][]) Array.newInstance(type.getClass().getComponentType(), z, y, x);
}

String[] arr1 = newArray(5, new String[0]);  //new String[5] と同じ
System.out.println("length = " + arr1.length);
System.out.println();

String[][] arr2 = newArray(2, 5, new String[0]);  //new String[2][5] と同じ
System.out.println("y length = " + arr2.length);
System.out.println("x length = " + arr2[0].length);
System.out.println();

String[][][] arr3 = newArray(3, 2, 5, new String[0]);  //new String[3][2][5] と同じ
System.out.println("z length = " + arr3.length);
System.out.println("y length = " + arr3[0].length);
System.out.println("x length = " + arr3[0][0].length);
System.out.println();

//Integer[] → int[] に変換する
public static final int[] toIntArray(final Integer[] src) {
    final int len = src.length;
    final int[] dst = new int[len];
    for (int i = 0; i < len; i++)
        dst[i] = (src[i] == null) ? 0 : src[i];
    return dst;
}

//Integer[] で生成（※要素が null なので使う際は注意）
Integer[] tmp = newArray(5, new Integer[0]);
for (int i = 0; i < tmp.length; i++)
    tmp[i] = i;  //連番で要素を初期化

//Integer[] → int[] に変換
int[] arr = toIntArray(tmp);
System.out.println("length = " + arr.length);

//要素を結合して表示
String s = "";
for (int e : arr) {
    if (s.length() > 0)
        s += ", ";
    s += e;
}
System.out.println(s);

import java.util.Arrays;

//Integer[] → int[] に変換
int[] arr = Arrays.stream(tmp).mapToInt(e -> e).toArray();  //Java 1.8 / Android 7.0[API 24]

/**<h1>整数の桁数を求める</h1>
 * <p>0 となるまで、10 で割り続ける方法。</p>
 * @param value ： 調べる値
 * @return<b>int</b> ： 桁数 (負の値は '-' を除いた桁数)
 */
public static final int length(long value) {
    int cnt = 0;
    do {
        cnt++;
        value /= 10;
    } while (value != 0);
    return cnt;
}


//メインでは...
int n = 1234;       //4
//int n = -4321;    //4
//int n = 0;        //1
System.out.println(length(n));

/**<h1>整数の桁数を求める</h1>
 * <p>0 となるまで、10 で割り続ける方法。</p>
 * @param value ： 調べる値
 * @return<b>int</b> ： 桁数 (負の値は '-' を除いた桁数)
 */
public static final int length(long value) {
    int cnt = 1;    //0 にも対応
    while ((value /= 10) != 0) {
        cnt++;
    }
    return cnt;
}


//メインでは...
int n = 1234;       //4
//int n = -4321;    //4
//int n = 0;        //1
System.out.println(length(n));

//int n = 1234;     //4
int n = -4321;      //4
//int n = 0;        //1

System.out.println(String.valueOf(Math.abs(n)).length());

/**<h1>x<sup>n</sup> の桁数を求める</h1>
 * <p>log10() により求める。底が負のときは NaN となるので注意。</p>
 * @param x ： 底 (> 0)
 * @param k ： べき指数 (>= 0)
 * @return<b>double</b> ： 桁数
 */
public static final double powLength(final double x, final double k) {
    return Math.floor(Math.log10(x) * k) + 1;
}


//メインでは...
int x = 2, k = 30;    //10.0
//int x = 123456789, k = 99999;    //809144.0
System.out.println(powLength(x, k));

/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗)の桁数を求める</h1>
 * <p>log10() により求める。底が負のときは NaN となるので注意。</p>
 * @param x ： 底 (> 0)
 * @param y ： べき指数1 (>= 0)
 * @param z ： べき指数2 (>= 0)
 * @return<b>double</b> ： 桁数 (オーバーフロー: Infinity に注意)
 */
public static final double powpowLength(final double x, final double y, final double z) {
    final double p = Math.log10(y) * z;    //y^z
    final double q = Math.log10(x);        //x^p
    return Math.floor(q * Math.pow(10, p)) + 1;
}


//メインでは...
int x = 2, y = 3, z = 5;    //74.0
//int x = 5, y = 6, z = 7;    //195667.0
System.out.println(powpowLength(x, y, z));

/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) の log10() を返す</h1>
 * <p>この値で比較すれば、大小関係がわかる。底が負のときは NaN となるので注意。</p>
 * @param x ： 底 (> 0)
 * @param y ： べき指数1 (>= 0)
 * @param z ： べき指数2 (>= 0)
 * @return<b>double</b> ： 底を10<sup>10</sup>に合わせた log10() を返す
 */
public static final double powpowLog10(final double x, final double y, final double z) {
    final double p = Math.log10(y) * z;            //y^z
    final double q = Math.log10(Math.log10(x));    //10^q = log10 x
    return p + q;
}

/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) 同士の大小の比較</h1>
 * <p>比較の関係値を返す(-1, 0, 1 のみ)。差分ではない。</p>
 * @param x1 ： 底 a (> 0)
 * @param y1 ： べき指数1 a (>= 0)
 * @param z1 ： べき指数2 a (>= 0)
 * @param x2 ： 底 b (> 0)
 * @param y2 ： べき指数1 b (>= 0)
 * @param z2 ： べき指数2 b (>= 0)
 * @return<b>int</b> ： -1 : a < b / 1 : a > b / 0 : a == b
 */
public static final int powpowCompare(final double x1, final double y1, final double z1, 
    final double x2, final double y2, final double z2) {

    final double a = powpowLog10(x1, y1, z1);
    final double b = powpowLog10(x2, y2, z2);
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    } else {
        return 0;
    }
}


//メインでは...
int x1 = 123456, y1 = 9876543, z1 = 24356891;	//Infinity
int x2 = 333333, y2 = 5555555, z2 = 22222222;	//Infinity
System.out.println(powpowLength(x1, y1, z1));
System.out.println(powpowLog10(x1, y1, z1));
System.out.println(powpowLength(x2, y2, z2));
System.out.println(powpowLog10(x2, y2, z2));
System.out.println(powpowCompare(x1, y1, z1, x2, y2, z2));

int x = 2, y = 3, z = 5;
int a = (int)Math.pow(y, z);
BigDecimal b = new BigDecimal(x).pow(a);
System.out.println(b.toString());
System.out.println(b.precision());
System.out.println(powpowLength(x, y, z));

import java.util.Arrays;

int n = 20;    //n 上限

//動的計画法
long[] dp = new long[n + 1];

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

//F(n)を表示
System.out.println("F(" + n + ") = " + dp[n]);

//数列を表示
System.out.println(Arrays.toString(dp));

int n = 20;

//F(n)を表示
System.out.println("F(" + n + ") = " + fibonacci(n));

//再帰関数
long fibonacci(int n) {
    if (n <= 1) {
        return  n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

import java.util.Arrays;

int n = 20;

long[] fib = new long[n + 1];  //メモ(グローバルに置く)

//F(n)を表示
System.out.println("F(" + n + ") = " + fibonacci(n));

//数列を表示
System.out.println(Arrays.toString(fib));

//メモ化再帰
long fibonacci(int n) {
    if (n <= 1) {
        return fib[n] = n;
    }
    if (fib[n] > 0) {
        return fib[n];
    }
    return fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

final double GOLDEN_RATIO = 1.618033988749895;  //黄金比
final double SQRT5 = Math.sqrt(5);  //√5

int n = 20;

//ビネの公式
//(上の式) n = 72 から誤差が出る
double ans1 = (Math.pow(1.0 + SQRT5, n) - Math.pow(1.0 - SQRT5, n)) / (Math.pow(2, n) * SQRT5);
System.out.println("F(" + n + ") = " + (long)ans1 + " (" + ans1 + ")");

//(下の式) n = 71 から誤差が出る
double ans2 = Math.floor(Math.pow(GOLDEN_RATIO, n) / SQRT5 + 0.5);
System.out.println("F(" + n + ") = " + (long)ans2 + " (" + ans2 + ")");

import java.math.BigDecimal;
import java.math.RoundingMode;

int n = 231;  //232 から誤差が出る

/** 任意精度実数の黄金比 (50桁) */
final BigDecimal BIG_DECIMAL_GOLDEN = new BigDecimal("1.61803398874989484820458683436563811772030917980576");

/** 任意精度実数の √5 (50桁) */
final BigDecimal BIG_DECIMAL_SQRT5 = new BigDecimal("2.23606797749978969640917366873127623544061835961152");

BigDecimal ans = BIG_DECIMAL_GOLDEN.pow(n).divide(BIG_DECIMAL_SQRT5, 50, RoundingMode.FLOOR).add(new BigDecimal(0.5));

System.out.println("F(" + n + ") = " + ans.setScale(0, RoundingMode.FLOOR) + " (" + ans + ")");

import java.math.BigDecimal;
import java.util.Arrays;

int n = 100;

BigDecimal[] dp = new BigDecimal[n + 1];

dp[0] = BigDecimal.ZERO;
dp[1] = BigDecimal.ONE;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1].add(dp[i - 2]);
}

//F(n)を表示
System.out.println("F(" + n + ") = " + dp[n]);

//数列を表示
System.out.println(Arrays.toString(dp));

/**<h1>３つ以上の最大公約数を求める[gcd(a, b, c,...)]</h1>
 * <p>ユークリッドの互除法の繰り返しで求める。</p>
 * @param param ： 数値1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]
 * @return<b>int</b> ： 最大公約数(なし=1[互いに素])
 */
public static final int gcd(final int... param) {
    final int len = param.length;
    int g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
    for (int i = 1; i < len - 1; i++) {
        g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
    }
    return g;
}


//メインでは...
int a = 12;
int b = 36;
int c = 60;
int d = 96;

int g1 = gcd(a, b);
int g2 = gcd(g1, c);
int g3 = gcd(g2, d);
System.out.println("g3 = " + g3);

int g = gcd(a, b, c, d);
System.out.println("g  = " + g);
System.out.println(g == g3);

/**<h1>３つ以上のパラメタに対応させた拡張ユークリッド互除法[ax + by + cz +... = gcd(a, b, c,...)]</h1>
 * <p>拡張ユークリッドの互除法の繰り返しで求める。</p>
 * @param param ： 数値 1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]
 * @return<b>int[]</b> ： {[0]:gcd, [1]:x, [2]:y, [3]z,...} 最大公約数(なし=1 [互いに素])と解 x, y, z...
 */
public static final int[] extgcd(final int... param) {
    final int len = param.length;
    final int[][] g = new int[len - 1][];
    g[0] = extgcd(param[0], param[1]);      //extgcd(a, b) は以前作ったもの
    for (int i = 1; i < len - 1; i++) {
        g[i] = extgcd(g[i - 1][0], param[i + 1]);    //extgcd(a, b) は以前作ったもの
    }

    //解の係数を展開する
    final int[] res = new int[len + 1];
    res[len] = g[len - 2][2];
    res[0] = g[len - 2][0];    //gcd

    int k = g[len - 2][1];
    for (int i = len - 3; i >= 0; i--) {
        res[i + 2] = g[i][2] * k;
        k *= g[i][1];
    }
    res[1] = k;
    return res;
}


//メインでは...
int a = 12;
int b = 16;
int c = 18;
int d = 21;

int[] g1 = extgcd(a, b);
System.out.println("g1 = " + g1[0] + ", x = " + g1[1] + ", y = " + g1[2]);
int[] g2 = extgcd(g1[0], c);
System.out.println("g2 = " + g2[0] + ", x = " + g2[1] + ", y = " + g2[2]);
int[] g3 = extgcd(g2[0], d);
System.out.println("g3 = " + g3[0] + ", x = " + g3[1] + ", y = " + g3[2]);

int[] g = extgcd(a, b, c, d);
System.out.println("g  = " + g[0] + ", w = " + g[1] + ", x = " + g[2] + ", y = " + g[3] + ", z = " + g[4]);

/**<h1>拡張ユークリッド互除法</h1>
 * <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
 * @param a ： 数値１(>0)
 * @param b ： 数値２(>0)
 * @return<b>int[]</b> ： {[0]:gcd, [1]:x, [2]:y}：最大公約数(なし=1 [互いに素])と解 x, y
 */
public static final int[] extgcd(int a, int b) {
    int x0 = 1, x1 = 0;
    int y0 = 0, y1 = 1;

    while (b != 0) {
        int q = a / b;
        int r = a % b;
        int x2 = x0 - q * x1;
        int y2 = y0 - q * y1;

        a = b; b = r;
        x0 = x1; x1 = x2;
        y0 = y1; y1 = y2;
    }

    return new int[]{a, x0, y0};
}


//メインでは...
int a = 12;
int b = 21;
int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];
System.out.println("g = " + g + ", x = " + x + ", y = " + y);
System.out.println(a + " * " + x + " + " + b + " * " + y + " = " + g);
int sum = a * x + b * y;
System.out.println(sum == g);

/**<h1>拡張ユークリッド互除法</h1>
 * <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
 * @param a ： 数値１(>0)
 * @param b ： 数値２(>0)
 * @param x ： 解 x (参照渡し用 new int[1] で作る)
 * @param y ： 解 y (参照渡し用 new int[1] で作る)
 * @return<b>int</b> ： 最大公約数(なし=1 [互いに素])
 */
public static final int extgcd(final int a, final int b, final int[] x, final int[] y) {
    int g = a;
    if (b != 0) {
        g = extgcd(b, a % b, y, x);
        y[0] -= (a / b) * x[0];
    } else {
        x[0] = 1;
        y[0] = 0;
    }
    return g;
}


//メインでは...
int a = 12;
int b = 21;
int[] x = new int[1];    //参照渡しにするため、要素１個で作る
int[] y = new int[1];    //参照渡しにするため、要素１個で作る
int g = extgcd(a, b, x, y);
System.out.println("g = " + g + ", x = " + x[0] + ", y = " + y[0]);
System.out.println(a + " * " + x[0] + " + " + b + " * " + y[0] + " = " + g);
int sum = a * x[0] + b * y[0];
System.out.println(sum == g);

int a = 4;    //入力
int b = 11;   //入力

int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];

if (g != 1) {
    System.out.println(-1);
} else {
    String ans = "" + ((x >= 0) ? x : 0);
    ans += " " + ((y >= 0) ? y : 0);
    ans += " " + ((x < 0) ? -x : 0);
    ans += " " + ((y < 0) ? -y : 0);
    System.out.println(ans);    //答え
}