結果
問題 | No.312 置換処理 |
ユーザー |
![]() |
提出日時 | 2017-06-28 20:20:47 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 4,107 bytes |
コンパイル時間 | 2,432 ms |
コンパイル使用メモリ | 79,832 KB |
実行使用メモリ | 39,464 KB |
最終ジャッジ日時 | 2024-11-15 12:16:50 |
合計ジャッジ時間 | 7,345 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.InputMismatchException;import java.io.OutputStream;import java.util.StringTokenizer;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.math.BigDecimal;/*** Built using CHelper plug-in* Actual solution is at the top*/public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;InputReader in = new InputReader(inputStream);PrintWriter out = new PrintWriter(outputStream);Task solver = new Task();solver.solve(1, in, out);out.close();}static class Task {public void solve(int testNumber, InputReader in, PrintWriter out) {long N = in.nextLong();int[] primses = sieveEratosthenes(1000000);long res=N;if(N%2==0) res=N/2;if(N%4==0) res=4;for(int i=1; i<primses.length; i++){if(N%primses[i]==0){if(primses[i]<res) res=primses[i];break;}}out.println(res);}}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=nint[] 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);}static class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}}}