ACdream 1114(莫比乌斯反演)
2024-10-10 15:02:22
传送门:Number theory
题意:给n个数,n 和 每个数的范围都是 1---222222,求n个数中互质的对数。
分析:处理出每个数倍数的个数cnt[i],然后进行莫比乌斯反演,只不过这里的F(i)=cnt[i]*(cnt[i]-1)/2.
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 222222
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
inline int read()
{
char ch=getchar();int x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
bool vis[N+];
int mu[N+],prime[N+],sum[N+];
void Mobius()
{
memset(vis,false,sizeof(vis));
mu[]=;
int tot=;
for(int i=;i<=N;i++)
{
if(!vis[i])
{
prime[tot++]=i;
mu[i]=-;
}
for(int j=;j<tot;j++)
{
if(i*prime[j]>N)break;
vis[i*prime[j]]=true;
if(i%prime[j]==)
{
mu[i*prime[j]]=;
break;
}
else
{
mu[i*prime[j]]=-mu[i];
}
}
}
for(int i=;i<=N;i++)sum[i]=sum[i-]+mu[i];
}
int num[N+],cnt[N+];
LL solve(int n)
{
LL res=;
for(int i=;i<=n;i++)
{
if(!cnt[i])continue;
res+=1LL*mu[i]*cnt[i]*(cnt[i]-)/;
}
return res;
} int main()
{
int n,x;
Mobius();
while(scanf("%d",&n)>)
{
memset(num,,sizeof(num));
memset(cnt,,sizeof(cnt));
int mx=;
for(int i=;i<=n;i++)
{
x=read();
num[x]++;
mx=max(x,mx);
}
for(int i=;i<=mx;i++)
for(int j=i;j<=mx;j+=i)
cnt[i]+=num[j];
LL ans=solve(mx);
printf("%lld\n",ans);
}
}
最新文章
- windows server 2008 r2 企业版 hyper v做虚拟化的相关问题处理
- Hawk 3.1 动态页面,ajax,瀑布流
- kafka性能基准测试
- spring boot properties
- myeclipse注册码生成器
- JS控制flash的播放
- nautilus-open-terminal很有用的插件--鼠标右键打开终端
- chrome,firefox
- SignTool.exe(签名工具)
- Android系统Surface机制的SurfaceFlinger服务简要介绍和学习计划
- 11gR2(11.2) RAC TAF Configuration for Admin and Policy Managed Databases (文档 ID 1312749.1)
- CodeForces 412D Giving Awards
- OpenSceneGraph几个重要功能节点练习
- Python的序列类型——List
- codeforces 13 b
- python下基于sokcet的tcp通信——入门篇
- Linux的远程管理
- Mac日常使用问题
- [Swift实际操作]七、常见概念-(13)使用UIScreen查询设备屏幕信息
- HALCON形状匹配(转)
热门文章
- 一起C语言中程序时序问题的排查过程
- Swift - 访问通讯录联系人(使用系统提供的通讯录交互界面)
- Android KeyCode(官方)
- Android 百度地图开发(二)--- 定位功能之MyLocationOverlay,PopupOverlay的使用
- python - Django: Converting an entire set of a Model's objects into a single dictionary - Stack Overflow
- Swift - 通过url地址打开web页面
- 开源解析器--ANTLR
- TestNg JAVA 自动化单元测试框架Demo
- Html.Partial(";";)与Html.RenderPartial(";";)区别
- linux shell中的单引号与双引号的区别(看完就不会有引号的疑问了)(转)