public class PowerN {
	// aのn乗の掛け算の回数を戻すメソッド
	static int power_n( int a, int n )
	{
		// 結果の初期化
		int result = 0;

		// nが2以上の場合
		if ( 2 <= n ) {
			// nが1場の場合
			switch ( n ) {
				case 2:
					// n=2の場合、a*aを戻す
					result += 1;
					break;

				default:
					int pow_num = power_n( a, n / 2);
					result += pow_num;
					result += 1;
	
					// nが奇数の場合
					if ( 1 == ( n % 2 ) ) {
						result += 1;
					}
					break;
			}
		}

		return result;
	}


	// メイン
	public static void main( String[] args ) {
		// 変数の宣言
		int a, n;
		int ans;

		// べき乗の計算
		a = 3;
		n = 19;
		ans = power_n( a, n );

		// 結果表示
		System.out.println( a + "の" + n + "乗に使う掛け算の回数は、" + ans );
	}
}