首页 > 代码库 > ACdreamoj1114(Number theory)莫比乌斯容斥
ACdreamoj1114(Number theory)莫比乌斯容斥
题意:给n个数,为有多少互质对;
解法:然后求出mou值,然后求出1,2,3...max的倍数的个数,每个出现在gcd中的对数(num[i]*(num[i]-1))/2,乘上mou值进行容斥计算。
代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=222225; const int INF=1000000007; LL num[Max]; LL rem[Max]; int mou[Max]; int n; void init() { for(LL i=2; i<Max; i++) if(!mou[i]) { mou[i]=i; for(LL j=i*i; j<Max; j+=i) mou[j]=i; } mou[1]=1; for(int i=2;i<Max;i++) { if(i/mou[i]%mou[i]==0) mou[i]=0; else { mou[i]=-mou[i/mou[i]]; } } } int main() { init(); while(scanf("%d",&n)==1) { memset(rem,0,sizeof rem); memset(num,0,sizeof num); int ma=0; for(int i=0; i<n; i++) { int a; scanf("%d",&a); ma=max(ma,a); rem[a]++; } ma++; for(int i=1; i<ma; i++) { for(int j=i; j<ma; j+=i) { num[i]+=rem[j]; } } LL ans=0; for(int i=1; i<ma; i++) { ans+=mou[i]*(num[i]*(num[i]-1))/2; } cout<<ans<<'\n'; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。