結果
問題 | No.1653 Squarefree |
ユーザー | cyclerecycle9 |
提出日時 | 2021-09-13 03:53:23 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 522 ms / 2,000 ms |
コード長 | 8,590 bytes |
コンパイル時間 | 2,736 ms |
コンパイル使用メモリ | 89,964 KB |
実行使用メモリ | 49,004 KB |
最終ジャッジ日時 | 2024-06-25 01:33:04 |
合計ジャッジ時間 | 18,768 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 509 ms
48,940 KB |
testcase_01 | AC | 112 ms
39,576 KB |
testcase_02 | AC | 102 ms
39,808 KB |
testcase_03 | AC | 112 ms
39,968 KB |
testcase_04 | AC | 114 ms
39,832 KB |
testcase_05 | AC | 106 ms
39,800 KB |
testcase_06 | AC | 112 ms
39,836 KB |
testcase_07 | AC | 114 ms
39,608 KB |
testcase_08 | AC | 102 ms
39,960 KB |
testcase_09 | AC | 98 ms
40,064 KB |
testcase_10 | AC | 99 ms
39,796 KB |
testcase_11 | AC | 323 ms
48,788 KB |
testcase_12 | AC | 324 ms
48,796 KB |
testcase_13 | AC | 519 ms
48,784 KB |
testcase_14 | AC | 499 ms
48,656 KB |
testcase_15 | AC | 503 ms
48,640 KB |
testcase_16 | AC | 509 ms
48,792 KB |
testcase_17 | AC | 514 ms
48,708 KB |
testcase_18 | AC | 500 ms
48,620 KB |
testcase_19 | AC | 496 ms
48,588 KB |
testcase_20 | AC | 505 ms
48,824 KB |
testcase_21 | AC | 500 ms
48,784 KB |
testcase_22 | AC | 507 ms
48,700 KB |
testcase_23 | AC | 495 ms
48,772 KB |
testcase_24 | AC | 522 ms
49,004 KB |
testcase_25 | AC | 512 ms
48,444 KB |
testcase_26 | AC | 492 ms
48,660 KB |
testcase_27 | AC | 520 ms
48,924 KB |
testcase_28 | AC | 496 ms
48,604 KB |
testcase_29 | AC | 500 ms
48,848 KB |
testcase_30 | AC | 489 ms
48,688 KB |
testcase_31 | AC | 477 ms
48,720 KB |
testcase_32 | AC | 489 ms
48,936 KB |
testcase_33 | AC | 495 ms
48,920 KB |
testcase_34 | AC | 498 ms
48,868 KB |
testcase_35 | AC | 500 ms
48,792 KB |
testcase_36 | AC | 115 ms
39,864 KB |
testcase_37 | AC | 102 ms
39,796 KB |
testcase_38 | AC | 100 ms
39,196 KB |
testcase_39 | AC | 114 ms
40,104 KB |
testcase_40 | AC | 116 ms
39,780 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=1000000010l; while ((to-from)>=1) { long mid=(to-from)/2+from; if (f(mid, ans[i])){ to=mid; } else { from=mid+1; } } if (to*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) ); } } }