nyoj CO-PRIME 莫比乌斯反演
2024-10-10 07:16:11
CO-PRIME
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
-
This problem is so easy! Can you solve it?
You are given a sequence which contains n integers a1,a2……an, your task is to find how many pair(ai, aj)(i < j) that ai and aj is co-prime.
- 输入
- There are multiple test cases.
Each test case conatains two line,the first line contains a single integer n,the second line contains n integers.
All the integer is not greater than 10^5. - 输出
- For each test case, you should output one line that contains the answer.
- 样例输入
-
3
1 2 3 - 样例输出
-
3 思路: http://blog.csdn.net/lyhvoyage/article/details/38455415应该是出题的人吧。
分析:莫比乌斯反演。
此题中,设F(d)表示n个数中gcd为d的倍数的数有多少对,f(d)表示n个数中gcd恰好为d的数有多少对,
则F(d)=∑f(n) (n % d == 0)
f(d)=∑mu[n / d] * F(n) (n %d == 0)
上面两个式子是莫比乌斯反演中的式子。
所以要求互素的数有多少对,就是求f(1)。
而根据上面的式子可以得出f(1)=∑mu[n] * F(n)。
所以把mu[]求出来,枚举n就行了,其中mu[i]为i的莫比乌斯函数。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 1e5+; int vis[N];
int mu[N];
int prime[N],cnt;
int date[N];
long long ys[N];
int num[N];
void init()
{
memset(vis,,sizeof(vis));
mu[] = ;
cnt = ;
for(int i=;i<N;i++)
{
if(!vis[i])
{
prime[cnt++] = i;
mu[i] = -;
}
for(int j = ;j<cnt&&i*prime[j]<N;j++)
{
vis[i*prime[j]] = ;
if(i%prime[j]) mu[i*prime[j]] = -mu[i];
else
{
mu [i *prime[j]] = ;
break;
}
}
}
}
int main()
{
int n,maxn;
init();
while(scanf("%d",&n)>)
{
memset(num,,sizeof(num));
memset(ys,,sizeof(ys));
maxn = -;
for(int i=;i<=n;i++){
scanf("%d",&date[i]);
num[date[i]] ++;
if(date[i]>maxn) maxn = date[i];
}
/***计算F(N)*/
for(int i=;i<=maxn;i++)
{
for(int j=i;j<=maxn;j=j+i)
{
ys[i] = ys[i] + num[j];
}
}
long long sum = ;
for(int i=;i<=maxn;i++){
long long tmp = (long long)ys[i] *( ys[i]- )/;
sum = sum + mu[i]*tmp;
} printf("%I64d\n",sum);
}
return ;
}
最新文章
- HTML5轻松实现搜索框提示文字点击消失---及placeholder颜色的设置
- CodeForces 676D代码 哪里有问题呢?
- 手机端touch事件 jquery模拟
- CSS3判断手机横屏竖屏
- spring-mvc.xml报错cvc-complex-type.2.4.c
- 新版PHP 7效能實測:Drupal 7能快70%,碎形計算大勝Ruby和Python
- ssh sftp scp命令
- 2015 Multi-University Training Contest 1 - 1001 OO’s Sequence
- mysql prepare语句使用
- WPF之Behavior
- 【转】IT职场人生系列之四:怎样写简历
- Ubuntu自带的vi编辑器太难用了,换
- 蝕刻技術(Etching Technology)
- 定义文件XML——从简单开始
- 关于对数组和指针的测试与分析OC
- windows下使用curl命令 &;&; 常用curl命令
- 如何方便的在windows测试python程序
- CDH搭建Hadoop集群(Centos7)
- image-set实现Retina屏幕下图片显示详细介绍
- 使用GIT管理UE4代码
热门文章
- 2-sat(and,or,xor)poj3678
- [原创]java WEB学习笔记65:Struts2 学习之路--Struts的CRUD操作( 查看 / 删除/ 添加) ModelDriven拦截器 paramter 拦截器
- Server.Transfer,Response.Redirect用法点睛
- paper 80 :目标检测的图像特征提取之(一)HOG特征
- MOPSO 多目标例子群优化算法
- Yii2下拉框实现
- 对Alexia(minmin)网友代码的评论及对“求比指定数大且最小的‘不重复数’问题”代码的改进
- html规范整体结构
- HTML5 webapp框架
- struts2 笔记02 文件上传、文件下载、类型转换器、国际化的支持