結果
問題 | No.1653 Squarefree |
ユーザー | cyclerecycle9 |
提出日時 | 2021-09-13 03:44:17 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,587 bytes |
コンパイル時間 | 2,640 ms |
コンパイル使用メモリ | 88,180 KB |
実行使用メモリ | 60,676 KB |
最終ジャッジ日時 | 2024-06-25 01:19:41 |
合計ジャッジ時間 | 17,615 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 96 ms
51,624 KB |
testcase_02 | AC | 101 ms
52,048 KB |
testcase_03 | AC | 106 ms
51,916 KB |
testcase_04 | AC | 114 ms
51,936 KB |
testcase_05 | AC | 100 ms
51,744 KB |
testcase_06 | AC | 111 ms
51,664 KB |
testcase_07 | AC | 114 ms
52,096 KB |
testcase_08 | AC | 100 ms
52,168 KB |
testcase_09 | AC | 105 ms
52,080 KB |
testcase_10 | AC | 100 ms
52,164 KB |
testcase_11 | AC | 294 ms
60,232 KB |
testcase_12 | AC | 285 ms
60,364 KB |
testcase_13 | AC | 460 ms
60,508 KB |
testcase_14 | AC | 454 ms
60,324 KB |
testcase_15 | AC | 460 ms
60,520 KB |
testcase_16 | AC | 448 ms
60,628 KB |
testcase_17 | AC | 468 ms
60,504 KB |
testcase_18 | AC | 460 ms
60,292 KB |
testcase_19 | AC | 473 ms
60,452 KB |
testcase_20 | AC | 459 ms
60,652 KB |
testcase_21 | AC | 477 ms
60,556 KB |
testcase_22 | AC | 465 ms
60,524 KB |
testcase_23 | AC | 461 ms
60,268 KB |
testcase_24 | WA | - |
testcase_25 | AC | 490 ms
60,080 KB |
testcase_26 | AC | 463 ms
60,408 KB |
testcase_27 | AC | 492 ms
60,664 KB |
testcase_28 | AC | 472 ms
60,428 KB |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 477 ms
60,456 KB |
testcase_32 | AC | 457 ms
60,496 KB |
testcase_33 | WA | - |
testcase_34 | AC | 484 ms
60,552 KB |
testcase_35 | AC | 448 ms
60,476 KB |
testcase_36 | AC | 99 ms
52,084 KB |
testcase_37 | WA | - |
testcase_38 | AC | 87 ms
51,504 KB |
testcase_39 | AC | 88 ms
51,648 KB |
testcase_40 | AC | 97 ms
51,888 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.*; public class Main { static final long MOD1=1000000007; static final long MOD=998244353; static int ans=0; public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); InputReader sc=new InputReader(System.in); long L = sc.nextLong(); long R = sc.nextLong(); boolean[] p = new boolean[1000001]; long[] ans = new long[(int) (R-L+1)]; for (int i = 0; i < ans.length; i++) { ans[i] = i + L; } long sum = 0; boolean[] ans_p = new boolean[(int)(R-L+1)]; Arrays.fill(ans_p, true); for (int i = 2; i < p.length; i++) { if(p[i])continue; long pp = (long)i; for (long j = ceil(L, pp)*pp; j <= R; j+=pp){ int k = (int) (j - L); int s = 0; while (ans[k]%pp==0) { ans[k]/=pp; s++; } if (s>=2){ ans_p[k] = false; } } for (int j = 2*i; j < p.length; j+=i){ p[j] = true; } } for (int i = 0; i < ans.length; i++) { if (ans_p[i]){ if (ans[i]==1) { sum++; continue; } long from=2l; long to=1000000000l; while ((to-from)>=1) { long mid=(to-from)/2+from; if (f(mid, ans[i])){ to=mid; } else { from=mid+1; } } if (to!=ans[i]){ sum++; } } } System.out.println(sum); } static boolean f(long mid,long X) { if (mid*mid<X) { return false; }else { return true; } } static long ceil(long a,long b){ return a%b==0?a/b:a/b+1; } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } } //funはlamda式で定義 //prodで取得,setで更新(一点加算なら更新でおk) //二ブタンも出来る //SegTree<Integer> segTree=new SegTree<Integer>(N, (x,y)->x+y, 0);使用例 class SegTree<S> { final int MAX; final int N; final java.util.function.BinaryOperator<S> op; final S E; final S[] data; @SuppressWarnings("unchecked") public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) { this.MAX = n; int k = 1; while (k < n) k <<= 1; this.N = k; this.E = e; this.op = op; this.data = (S[]) new Object[N << 1]; java.util.Arrays.fill(data, E); } public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) { this(dat.length, op, e); build(dat); } private void build(S[] dat) { int l = dat.length; System.arraycopy(dat, 0, data, N, l); for (int i = N - 1; i > 0; i--) { data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]); } } public void set(int p, S x) { exclusiveRangeCheck(p); data[p += N] = x; p >>= 1; while (p > 0) { data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]); p >>= 1; } } public S get(int p) { exclusiveRangeCheck(p); return data[p + N]; } public S prod(int l, int r) { if (l > r) { throw new IllegalArgumentException( String.format("Invalid range: [%d, %d)", l, r) ); } inclusiveRangeCheck(l); inclusiveRangeCheck(r); S sumLeft = E; S sumRight = E; l += N; r += N; while (l < r) { if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]); if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight); l >>= 1; r >>= 1; } return op.apply(sumLeft, sumRight); } public S allProd() { return data[1]; } public int maxRight(int l, java.util.function.Predicate<S> f) { inclusiveRangeCheck(l); if (!f.test(E)) { throw new IllegalArgumentException("Identity element must satisfy the condition."); } if (l == MAX) return MAX; l += N; S sum = E; do { l >>= Integer.numberOfTrailingZeros(l); if (!f.test(op.apply(sum, data[l]))) { while (l < N) { l = l << 1; if (f.test(op.apply(sum, data[l]))) { sum = op.apply(sum, data[l]); l++; } } return l - N; } sum = op.apply(sum, data[l]); l++; } while ((l & -l) != l); return MAX; } public int minLeft(int r, java.util.function.Predicate<S> f) { inclusiveRangeCheck(r); if (!f.test(E)) { throw new IllegalArgumentException("Identity element must satisfy the condition."); } if (r == 0) return 0; r += N; S sum = E; do { r--; while (r > 1 && (r & 1) == 1) r >>= 1; if (!f.test(op.apply(data[r], sum))) { while (r < N) { r = r << 1 | 1; if (f.test(op.apply(data[r], sum))) { sum = op.apply(data[r], sum); r--; } } return r + 1 - N; } sum = op.apply(data[r], sum); } while ((r & -r) != r); return 0; } private void exclusiveRangeCheck(int p) { if (p < 0 || p >= MAX) { throw new IndexOutOfBoundsException( String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX) ); } } private void inclusiveRangeCheck(int p) { if (p < 0 || p > MAX) { throw new IndexOutOfBoundsException( String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX) ); } } }