fork download
copy 
  1. import java.io.*;
  2. import java.util.Locale;
  3. import java.util.StringTokenizer;
  4.  
  5. public class TaskC {
  6.     private final InputReader reader;
  7.     private final OutputWriter writer;
  8.  
  9.     public TaskC(InputReader reader, OutputWriter writer) {
  10.         this.reader = reader;
  11.         this.writer = writer;
  12.     }
  13.  
  14.     public static void main(String[] args) {
  15.         InputReader reader = new InputReader(System.in);
  16.         OutputWriter writer = new OutputWriter(System.out);
  17.         new TaskC(reader, writer).run();
  18.         writer.writer.flush();
  19.     }
  20.  
  21.     final int M = 500 * 1000;
  22.  
  23.     int[][] factors;
  24.  
  25.     int[] cnt = new int[M];
  26.     long ans = 0;
  27.  
  28.     int[] in = new int[M];
  29.  
  30.     void add(int x, int mul) {
  31.         for (int f : factors[x]) {
  32.             int g = (f < 0) ? -f : f;
  33.             int h = (f < 0) ? -1 : 1;
  34.             if (mul == 1) {
  35.                 ans += mul * h * cnt[g];
  36.                 cnt[g] += mul;
  37.             } else {
  38.                 cnt[g] += mul;
  39.                 ans += mul * h * cnt[g];
  40.             }
  41.         }
  42.     }
  43.  
  44.     public void run() {
  45.         factors = new int[M + 1][];
  46.         for (int x = 1; x <= M; x++) {
  47.             int[] f = new int[6];
  48.             int fpt = 0;
  49.             int y = x;
  50.             for (int i = 2; i * i <= y; i++)
  51.                 if (y % i == 0) {
  52.                     if (fpt == 6)
  53.                         throw new AssertionError();
  54.                     f[fpt++] = i;
  55.                     while (y % i == 0)
  56.                         y /= i;
  57.                 }
  58.             if (y != 1) {
  59.                 if (fpt == 6)
  60.                     throw new AssertionError();
  61.                 f[fpt++] = y;
  62.             }
  63.             factors[x] = new int[1 << fpt];
  64.             for (int msk = 0; msk < (1 << fpt); msk++) {
  65.                 factors[x][msk] = (1 - (Integer.bitCount(msk) % 2) * 2);
  66.                 for (int j = 0; j < fpt; j++)
  67.                     if (((msk >> j) & 1) == 1)
  68.                         factors[x][msk] *= f[j];
  69.             }
  70.         }
  71.         int n = reader.nextInt();
  72.         int[] A = new int[n];
  73.         int q = reader.nextInt();
  74.         for (int i = 0; i < n; i++)
  75.             A[i] = reader.nextInt();
  76.         for (int i = 0; i < q; i++) {
  77.             int j = reader.nextInt() - 1;
  78.             add(A[j], 1 - 2 * in[j]);
  79.             in[j] = 1 - in[j];
  80.             writer.printf("%d\n", ans);
  81.         }
  82.     }
  83.  
  84.  
  85.     static class InputReader {
  86.         public BufferedReader reader;
  87.         public StringTokenizer tokenizer;
  88.  
  89.         public InputReader(InputStream stream) {
  90.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  91.             tokenizer = null;
  92.         }
  93.  
  94.         public String next() {
  95.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  96.                 try {
  97.                     tokenizer = new StringTokenizer(reader.readLine());
  98.                 } catch (IOException e) {
  99.                     throw new RuntimeException(e);
  100.                 }
  101.             }
  102.             return tokenizer.nextToken();
  103.         }
  104.  
  105.         public int nextInt() {
  106.             return Integer.parseInt(next());
  107.         }
  108.  
  109.         public double nextDouble() {
  110.             return Double.parseDouble(next());
  111.         }
  112.  
  113.         public long nextLong() {
  114.             return Long.parseLong(next());
  115.         }
  116.     }
  117.  
  118.     static class OutputWriter {
  119.         public PrintWriter writer;
  120.  
  121.         OutputWriter(OutputStream stream) {
  122.             writer = new PrintWriter(stream);
  123.         }
  124.  
  125.         public void printf(String format, Object... args) {
  126.             writer.print(String.format(Locale.ENGLISH, format, args));
  127.         }
  128.     }
  129. }
  130.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class TaskC is public, should be declared in a file named TaskC.java
public class TaskC {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/De4DCl
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!