【bzoj4146】[AMPPZ2014]Divisors 数论
2024-09-08 02:29:05
原文地址:http://www.cnblogs.com/GXZlegend/p/6801411.html
题目描述
给定一个序列a[1],a[2],...,a[n]。求满足i!=j且a[i]|a[j]的二元组(i,j)的个数。
输入
第一行包含一个正整数n(1<=n<=2000000),表示序列长度。
第二行包含n个正整数,依次表示a[1],a[2],...,a[n](1<=a[i]<=2000000)。
输出
一个整数,即满足条件的二元组的个数。
样例输入
5
2 4 5 2 6
样例输出
6
题解
数论
根据微积分什么的能得出n/1+n/2+...+n/n<n(ln n+1)
然后枚举1到maxa的每个数。
由于两个相同的数符合条件,则当有n个相同的数时二元组个数为n(n-1)。
再依次向上查找该数的倍数,二元组个数为n1*n2。
然后加起来就好了。
#include <cstdio>
#include <algorithm>
using namespace std;
long long v[2000010];
int main()
{
int n , m = 0 , i , j , x;
long long ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
scanf("%d" , &x) , v[x] ++ , m = max(m , x);
for(i = 1 ; i <= m ; i ++ )
{
ans += v[i] * (v[i] - 1);
for(j = 2 * i ; j <= m ; j += i) ans += v[i] * v[j];
}
printf("%lld\n" , ans);
return 0;
}
最新文章
- MapReduce编程示例
- mybatis map foreach遍历
- Excel 统计在某个区间内数值的个数
- Javascript的一个生产PDF的库: unicode和中文问题的解决
- IntelliJ IDEA Community Edition 14.1.4下 javafx scenebuilder的使用
- PostgreSQL的 initdb 源代码分析之四
- uva 11646 - Athletics Track
- Java Web应用的开发模式
- Android ViewPager PagerAdapter 图片轮播
- cxSpreadBook 要么 cxSpreadSheet 设置文本格式
- Dynamics 365 Online 试用账号申请方式
- 安装VirtualBox中的增强功能包VBoxLinuxAdditions
- magento 2 method config
- spring+springMVC+mybatis简单整合
- 【洛谷 P1616 疯狂的采药】
- Codeforces 830C Bamboo Partition (看题解)
- js-BootstrapValidator简单使用
- centos6.5(64bit),python2.6.6安装MySQLdb模块
- Linux 创建用户 限制SFTP用户只能访问某个目录
- 解决mysql安装出现error Nr.1045问题