【zzulioj 1902 985的因子对难题】
发布日期:2021-11-04 12:58:46 浏览次数:5 分类:技术文章

本文共 1035 字,大约阅读时间需要 3 分钟。

985的因子对难题

Description

985有n个正整数,他想知道存在多少个不同的因子对(a[i], a[j])使得

1 <= i, j <= n && i != j && a[j] % a[i] == 0,其中i和j是元素的下标。
特别地,他认为(a[i],a[j])与(a[j],a[i])是一样的因子对。
Input

第一行输入一个整数t,代表有t组测试数据。

每组数据占两行,第一行输入一个n代表元素个数,下面一行输入n个整数a[]。
注:1 <= t <= 30,1 <= n <= 1e5,1 <= a[] <= 1e6。
Output

一个整数代表最后的答案。

Sample Input

2

5
1 2 3 4 5
5
2 2 2 2 2
Sample Output

5

10
HINT

Source

hpu

因子对数=该数的倍数的个数×该数的个数+该数的个数×(该数的个数-1)/2;

#include
#include
using namespace std;const int INF=0x3f3f3f3f;int pa[100011];int main(){ int ans,T,N,i,j,a,num; scanf("%d",&T); while(T--) { num=0; scanf("%d",&N); for(i=1;i<=100011;i++) pa[i]=0; for(i=1;i<=N;i++) { scanf("%d",&a); pa[a]++; num=max(num,a); } ans=0; for(i=1;i<=num;i++) { if(pa[i]) { for(j=i*2;j<=num;j+=i) ans+=pa[i]*pa[j]; ans+=pa[i]*(pa[i]-1)/2; } } printf("%d\n",ans); } return 0;}

转载地址:https://blog.csdn.net/WYK1823376647/article/details/52247709 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【zzulioj 1912 小火山的爱情密码】
下一篇:【zzulioj 1921 】

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月19日 22时20分12秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章