Submission #846995


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.HashSet;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ilyakor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        static final long BUBEN = (long) (1E11);

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            //int n = 1000 * 100;
            int[] pr = PrimesGenerator.getPrimes(101000);

            HashSet<Long> prs = new HashSet<>();
            for (int p : pr) prs.add((long) p);
            HashSet<Long> prs2 = new HashSet<>();
            for (int p : pr) prs2.add((long) p * (long) p);

            HashMap<Long, Integer> d = new HashMap<>();
            HashMap<Long, Long> op = new HashMap<>();
            for (int i = 0; i < n; ++i) {
                long x = in.nextLong();
                //long x = 9999999967L;
                long y = 1, oy = 1;
                if (prs.contains(x)) {
                    y *= x;
                    oy *= x;
                    oy *= x;
                } else if (prs2.contains(x)) {
                    y *= x;
                    long s = (long) Math.sqrt(x) - 3;
                    if (s < 0) s = 0;
                    while (s * s < x) ++s;
                    oy *= s;
                } else {
                    for (int p : pr) {
                        if (p > x) break;
                        if (p > 4000) {
//                        long up = (long)Math.pow(2E10 / x, 2.0 / 3.0) + 10;
//                        if (p > up) break;
                            break;
                        }
                        int c = 0;
                        while (x % p == 0) {
                            x /= p;
                            ++c;
                        }
                        c %= 3;
                        if (c == 0) continue;
                        if (c == 1) {
                            y *= p;
                            oy *= p;
                            if (oy > BUBEN) oy = 0;
                            oy *= p;
                            if (oy > BUBEN) oy = 0;
                        } else {
                            y *= p;
                            y *= p;
                            oy *= p;
                            if (oy > BUBEN) oy = 0;
                        }
                    }
                    if (x != 1) {
                        if (prs.contains(x)) {
                            y *= x;
                            oy *= x;
                            if (oy > BUBEN) oy = 0;
                            oy *= x;
                            if (oy > BUBEN) oy = 0;
                        } else if (prs2.contains(x)) {
                            y *= x;
                            long s = (long) Math.sqrt(x) - 3;
                            if (s < 0) s = 0;
                            while (s * s < x) ++s;
                            oy *= s;
                            if (oy > BUBEN) oy = 0;
                        } else {
                            y *= x;
                            oy = 0;
                        }
                    }
                }


                if (d.containsKey(y)) {
                    d.put(y, d.get(y) + 1);
                } else {
                    d.put(y, 1);
                    op.put(y, oy);
                }
            }

            HashSet<Long> used = new HashSet<>();
            int res = 0;
            for (long x : d.keySet()) {
                if (x == 1) {
                    ++res;
                    continue;
                }
                if (used.contains(x)) continue;
                long ox = op.get(x);
                int val = d.get(x);
                int oval = d.containsKey(ox) ? d.get(ox) : 0;
                res += Math.max(val, oval);
                used.add(x);
                used.add(ox);
            }
            out.printLine(res);
        }

    }

    static class PrimesGenerator {
        public static int[] getPrimes(int n) {
            boolean[] prime = new boolean[n + 1];
            Arrays.fill(prime, 2, n + 1, true);
            for (int i = 2; i * i <= n; i++) {
                if (prime[i]) {
                    for (int j = i * i; j <= n; j += i) {
                        prime[j] = false;
                    }
                }
            }
            int[] primes = new int[n + 1];
            int cnt = 0;
            for (int i = 0; i < prime.length; i++)
                if (prime[i])
                    primes[cnt++] = i;

            return Arrays.copyOf(primes, cnt);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buffer = new byte[10000];
        private int cur;
        private int count;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isSpace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (count == -1) {
                throw new InputMismatchException();
            }
            try {
                if (cur >= count) {
                    cur = 0;
                    count = stream.read(buffer);
                    if (count <= 0)
                        return -1;
                }
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            return buffer[cur++];
        }

        public int readSkipSpace() {
            int c;
            do {
                c = read();
            } while (isSpace(c));
            return c;
        }

        public int nextInt() {
            int sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10 + c - '0';
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

        public long nextLong() {
            long sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10L + (long) (c - '0');
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

    }
}

Submission Info

Submission Time
Task D - Anticube
User ilyakor
Language Java8 (OpenJDK 1.8.0)
Score 1100
Code Size 8499 Byte
Status AC
Exec Time 2439 ms
Memory 49600 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 3
AC × 51
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 2395 ms 46888 KB
02.txt AC 2144 ms 46012 KB
03.txt AC 2211 ms 47032 KB
04.txt AC 2195 ms 47364 KB
05.txt AC 2215 ms 45816 KB
06.txt AC 2079 ms 46872 KB
07.txt AC 2143 ms 45952 KB
08.txt AC 2439 ms 46628 KB
09.txt AC 2135 ms 45148 KB
10.txt AC 2087 ms 47064 KB
11.txt AC 1466 ms 29244 KB
12.txt AC 1479 ms 33348 KB
13.txt AC 1403 ms 35608 KB
14.txt AC 1463 ms 35028 KB
15.txt AC 1411 ms 33048 KB
16.txt AC 1323 ms 35428 KB
17.txt AC 390 ms 22544 KB
18.txt AC 379 ms 22188 KB
19.txt AC 395 ms 22484 KB
20.txt AC 383 ms 22200 KB
21.txt AC 1679 ms 38824 KB
22.txt AC 1663 ms 37864 KB
23.txt AC 1591 ms 38776 KB
24.txt AC 1665 ms 38992 KB
25.txt AC 1699 ms 42052 KB
26.txt AC 1623 ms 37952 KB
27.txt AC 1187 ms 49600 KB
28.txt AC 263 ms 14544 KB
29.txt AC 275 ms 15056 KB
30.txt AC 299 ms 16344 KB
31.txt AC 279 ms 16116 KB
32.txt AC 299 ms 15996 KB
33.txt AC 179 ms 10708 KB
34.txt AC 363 ms 20940 KB
35.txt AC 355 ms 21824 KB
36.txt AC 191 ms 10576 KB
37.txt AC 1759 ms 30280 KB
38.txt AC 1823 ms 31668 KB
39.txt AC 1895 ms 33896 KB
40.txt AC 1855 ms 31196 KB
41.txt AC 191 ms 10452 KB
42.txt AC 183 ms 10452 KB
43.txt AC 183 ms 10444 KB
44.txt AC 280 ms 10708 KB
45.txt AC 191 ms 10572 KB
46.txt AC 179 ms 10448 KB
47.txt AC 195 ms 10452 KB
48.txt AC 191 ms 10708 KB
s1.txt AC 179 ms 10452 KB
s2.txt AC 200 ms 10580 KB
s3.txt AC 175 ms 10576 KB