E. Mike and Foam(容斥原理)「建议收藏」

E. Mike and Foam(容斥原理)

大家好,又见面了,我是全栈君。

E. Mike and Foam

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 ai milliliters of foam on it.


E. Mike and Foam(容斥原理)「建议收藏」

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 < j and E. Mike and Foam(容斥原理)「建议收藏」 where E. Mike and Foam(容斥原理)「建议收藏」 is the greatest common divisor of numbers a and b.

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

Input

The first line of input contains numbers n and q (1 ≤ n, q ≤ 2 × 105), the number of different kinds of beer and number of queries.

The next line contains n space separated integers, a1, a2, … , an (1 ≤ ai ≤ 5 × 105), 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.

Output

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

Sample test(s)
Input
5 6
1 2 3 4 6
1
2
3
4
5
1

Output
0
1
3
5
6
2

题意简单易懂,我就不说了。。。

题解:题目能够转化为,在一个动态的集合中。没增加一个数。或取出一个数后,剩下的数中互质的有多少对。注意是无序的。 由于在题目的数据范围内质因子的数量非常少,复杂度基本上能够忽略不计,所以我们能够对每个新加进去的数。或者取出来的数进行质因子分解。然后通过容斥原理,先算出集合中有多少个与其不互质,这个非常easy算出来吧!

(假设想不出来能够看下我的代码,就是通过一个数组来计数,挺简单)。知道了不互质的。自然就知道互质了辣!

然后就答案减去或者加上互质的数就能够了。 时间复杂度预计10^7级别。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116365.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • document.getElementById 用法

    document.getElementById 用法 document.getElementById使用   注意:document.getElementById(“”)得到的是一个对象,用alert显示得到的是“object”,而不是具体的值,它有value和length等属性,加上.value得到的才是具体的值! 参考资料:1.docum

  • [POJ 2976]Dropping tests(0-1分数规划)

    [POJ 2976]Dropping tests(0-1分数规划)

  • 关于MSHTML (转)

    关于MSHTML(转)[@more@]microsoft.com/default.ASP”target=_top>MSDNHome>MSDNLibrary>ProgrammingandR…

  • python:set() 函数[通俗易懂]

    python:set() 函数[通俗易懂]描述Python内置函数创建一个无序不重复元素集可进行关系测试,删除重复数据集合对象还支持union(联合),intersection(交),difference(差)和sysmmetr

  • numpy.meshgrid()理解

    numpy.meshgrid()理解一句话解释numpy.meshgrid()——生成网格点坐标矩阵。关键词:网格点,坐标矩阵网格点是什么?坐标矩阵又是什么鬼?我先问个问题:这张图你会生成吗?…

  • hibernate和mybatisplus区别_hibernate sql

    hibernate和mybatisplus区别_hibernate sql摘抄自:《javaEE互联网轻量级框架整合开发》MyBatis因为具有封装少,映射多样化,支持存储过程,可以进行SQL优化等特点。使得它取代了Hibernate成为了java互联网中首选的持久框架。无论MyBatis或Hibernate都可以称为ORM框架,Hibernate的设计理念是完全面向POJO的,而MyBatis不是。Hibernate基本不再需要编写SQL就可以通过映射关系来操作…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号