#232246 (Java21) No.639 An Ordinary Sequence

• 問題: No.639 An Ordinary Sequence
• ユーザー: tetsu
• 提出日時: 2018-01-27 02:55:03
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 165 ms / 1,000 ms
• コード長: 615 bytes
• コンパイル時間: 3,380 ms
• コンパイル使用メモリ: 72,216 KB
• 実行使用メモリ: 61,948 KB
• 最終ジャッジ日時: 2023-08-30 12:52:06
• 合計ジャッジ時間: 7,407 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	165 ms; 61,908 KB
testcase_01	AC	163 ms; 61,896 KB
testcase_02	AC	146 ms; 61,704 KB
testcase_03	AC	143 ms; 61,820 KB
testcase_04	AC	143 ms; 59,824 KB
testcase_05	AC	145 ms; 61,604 KB
testcase_06	AC	143 ms; 61,832 KB
testcase_07	AC	142 ms; 61,788 KB
testcase_08	AC	140 ms; 61,748 KB
testcase_09	AC	143 ms; 61,948 KB
testcase_10	AC	142 ms; 61,664 KB
testcase_11	AC	140 ms; 61,780 KB
testcase_12	AC	149 ms; 61,632 KB
testcase_13	AC	148 ms; 61,444 KB
testcase_14	AC	148 ms; 61,756 KB
testcase_15	AC	152 ms; 61,752 KB
testcase_16	AC	162 ms; 61,448 KB
testcase_17	AC	146 ms; 61,672 KB
testcase_18	AC	163 ms; 61,884 KB

ソースコード

package yukicoder;
import java.util.*;

public class P639 {
	static int memory = 1000000;
	static long[] memo = new long[memory];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		Arrays.fill(memo, -1);
		memo[0] = 1;
		for(int i=1; i<memory; i++) {
			memo[i] = memo[i/3]+memo[i/5]; 
		}
		System.out.println(a(n));
	}
	
	static public long a(long n) {
		if(n==0) {
			return 1;
		}
		if(n<memory&&memo[(int)n]!=-1) {
			return memo[(int)n];
		}
		if(n/3==n/5) {
			return 2*a(n/3);
		}
		return a(n/3)+a(n/5);
	}

}