fork download
  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
stdin
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
Standard output is empty