結果

問題 No.2610 Decreasing LCMs
コンテスト
ユーザー uwi
提出日時 2024-01-20 17:30:22
言語 Java
(openjdk 23)
結果
AC  
実行時間 165 ms / 1,000 ms
コード長 2,815 bytes
コンパイル時間 4,076 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 42,140 KB
最終ジャッジ日時 2024-09-28 05:41:49
合計ジャッジ時間 8,793 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no2xxx;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class No2610_2 {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int[] a = new int[25];
		a[0] = 720719;
		a[1] = 720720;
		outer:
		for(int i = 2;i < 25;i++){
			for(a[i] = a[i-1] + a[i-1] - a[i-2] + 1;;a[i]++){
				int t = a[i] - a[i-1];
				if(a[i] % t == 0 && a[i-2] / (a[i-1] - a[i-2]) > a[i] / (a[i] - a[i-1])){
//					tr(a);
					continue outer;
				}
			}
		}
//		tr(a);
		int n = ni();
		for(int i = 0;i < n;i++){
			out.print(a[i] + " ");
		}
		out.println();
	}

	public static int gcd(int a, int b) {
		while (b > 0) {
			int c = a;
			a = b;
			b = c % b;
		}
		return a;
	}


	public static boolean inc(int[] a, int base) {
		int n = a.length;
		int i;
		for (i = n - 1; i >= 0 && a[i] == base - 1; i--) ;
		if (i == -1) return false;

		a[i]++;
		Arrays.fill(a, i + 1, n, 0);
		return true;
	}


	public static int[] sieveEratosthenes(int n) {
		if (n <= 32) {
			int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
			for (int i = 0; i < primes.length; i++) {
				if (n < primes[i]) {
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}

		int u = n + 32;
		double lu = Math.log(u);
		int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
		ret[0] = 2;
		int pos = 1;

		int[] isnp = new int[(n + 1) / 32 / 2 + 1];
		int sup = (n + 1) / 32 / 2 + 1;

		int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
		for (int tp : tprimes) {
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31);
			for (int j = 0; j < sup; j += tp) {
				for (int i = 0; i < tp && i + j < sup; i++) {
					isnp[j + i] |= ptn[i];
				}
			}
		}

		// 3,5,7
		// 2x+3=n
		int[] magic = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14};
		int h = n / 2;
		for (int i = 0; i < sup; i++) {
			for (int j = ~isnp[i]; j != 0; j &= j - 1) {
				int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
				int p = 2 * pp + 3;
				if (p > n) break;
				ret[pos++] = p;
				if ((long) p * p > n) continue;
				for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q;
			}
		}

		return Arrays.copyOf(ret, pos);
	}


	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static long nl() { return Long.parseLong(in.next()); }
	static double nd() { return Double.parseDouble(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
0