当前位置:首页 > 数学 > 筛法 > 正文
洛谷P7517[省选联考2021B卷]数对
218+

题目大意:n个正整数,有多少个满足倍数关系的数对?

题目描述

给定 $n$ 个正整数 $a_i$,请你求出有多少个数对 $(i, j)$ 满足 $1 \le i \le n$,$1 \le j \le n$,$i \ne j$ 且 $a_i$ 是 $a_j$ 的倍数。

输入输出格式

输入格式

第一行,一个整数 $n$,表示数字个数。
第二行,$n$ 个整数,表示 $a_i$。

输出格式

输出一行,一个整数,表示答案。

输入输出样例

输入样例 #1

6
16 11 6 1 9 11

输出样例 #1

7

输入样例 #2

见附件中的 pair/pair2.in。

输出样例 #2

见附件中的 pair/pair2.ans。

说明

对于 $40 \%$ 的数据,$n \le 1000$。
对于 $70 \%$ 的数据,$1 \le a_i \le 5 \times {10}^3$。
对于 $100 \%$ 的数据,$2 \le n \le 2 \times {10}^5$,$1 \le a_i \le 5 \times {10}^5$。

解题思路

枚举每个数字,找跟他配对的另一个数字。可以用筛法翻倍查找,这样总体时间复杂度是$O(nlog_2n)$。需要注意的是,1倍是自己,同等大小的数字有很多个,需要减去自己,因为不能自己跟自己配对。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P7517[省选联考2021B卷]数对:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter