Mike and Foam

题面翻译

题目描述

$Mike$是$Rico$酒吧的调酒师。在$Rico$酒吧，他们将啤酒杯放在一个特殊的架子上。在$Rico$酒吧，有$n$种啤酒编号从$1$到$n$。第$i$瓶啤酒上面有$a_{i}$ 毫升的泡沫。

$Maxim$是$Mike$的老板。今天他让$Mike$回答$q$个查询。最初架子是空的。在每个操作中，$Maxim$给他一个编号$X$。如果编号为$X$的啤酒已经在架子上，那么$Mike$应该从架子上取下它，否则他应该把它放在架子上。

每次询问后，$Mike$应该告诉他架子的分数。他们认为货架的分数是满足$i<j$并且$gcd(a_{i},a_{j})=1$的数对$(i,j)$的个数。

$Mike$现在很累。所以他请你帮他处理这些操作。

输入格式

第一行输入包含数字$n$和$q$（$1\le n$，$q\le 2\times {10}^{5}$），不同种类的啤酒数量和查询次数。

下一行包含$n$个由空格分隔的整数，$a_{1},a_{2},\dots,a_{n}$($1\le a_{i}\le 5\times10^{5}$ ），表示各种啤酒顶部的泡沫量。

接下来$q$行一行包含一个查询。每个查询一个整数$X$（$1\le X\le N$），表示应从货架上添加或移除的啤酒的编号。

输出格式

对于每一个查询，用一行输出对应的答案。

题目描述

Mike is a bartender at Rico's bar. At Rico's, they put beer glasses in a special shelf. There are $n$ kinds of beer at Rico's numbered from $1$ to $n$ . $i$ -th kind of beer has $a_{i}$ milliliters of foam on it.

Maxim is Mike's boss. Today he told Mike to perform $q$ queries. Initially the shelf is empty. In each request, Maxim gives him a number $x$ . If beer number $x$ is already in the shelf, then Mike should remove it from the shelf, otherwise he should put it in the shelf.

After each query, Mike should tell him the score of the shelf. Bears are geeks. So they think that the score of a shelf is the number of pairs $(i,j)$ of glasses in the shelf such that i&lt;j and where is the greatest common divisor of numbers $a$ and $b$ .

Mike is tired. So he asked you to help him in performing these requests.

输入格式

The first line of input contains numbers $n$ and $q$ ( $1<=n,q<=2×10^{5}$ ), the number of different kinds of beer and number of queries.

The next line contains $n$ space separated integers, $a_{1},a_{2},...\ ,a_{n}$ ( $1<=a_{i}<=5×10^{5}$ ), the height of foam in top of each kind of beer.

The next $q$ lines contain the queries. Each query consists of a single integer integer $x$ ( $1<=x<=n$ ), the index of a beer that should be added or removed from the shelf.

输出格式

For each query, print the answer for that query in one line.

样例 #1

样例输入 #1

5 6
1 2 3 4 6
1
2
3
4
5
1

样例输出 #1

0
1
3
5
6
2