【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 Output5
10 HINTSource
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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月19日 22时20分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
mysql 查询姓王_MySQL查询语句练习题,测试足够用了
2019-04-21
mysql多实例脚本_mysql多实例脚本
2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构
2019-04-21
mysql加密复制_MySQL主从复制使用SSL加密
2019-04-21
python启动远端 exe_python打包exe开机自动启动的实例(windows)
2019-04-21
java当前路径_java获取当前路径的几种方法
2019-04-21
java web传递参数_Javaweb的八种传值方式
2019-04-21
java gui支持的包有哪两个_Java GUI
2019-04-21
java list详解_java集合List解析
2019-04-21
java坐标代码_java实现计算地理坐标之间的距离
2019-04-21
mysql 取两个时间差 php_在php和MySql中计算时间差的方法详解
2019-04-21
mysql 重启数据库实例_mysql 单机多实例重启数据库服务
2019-04-21
dtc mysql_DTCC归来-高可用可扩展数据库架构探讨
2019-04-21
java怎样将日期本土化_Java中的日期操作
2019-04-21
java生产者消费者模型到精通_java生产者消费者模型
2019-04-21