http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82839#problem/C
14年鞍山区域赛的题...
记得是当时全场过得第四多的题...
讲题的时候丽洁姐说“莫比乌斯反演blablabla”
当时完全不懂==
嗯，第一次接触了莫比乌斯反演这个东西。。。好像这个东西在数论中挺重要的。
这道题需要注意的是，求和x的互质的个数的时候，1和任何正整数都是互质的，但是1和1互质这一组是不符合条件的....记得判断下。
求Mobius函数好像有一个筛法求（见贾志鹏线性筛.pdf），然后红书上有一个递推求1~n的mobius函数值的方法（见红书23）；
然后被强制转化类型坑了2发WA。。。要开long long ,不写强制转换就会WA。。。还没搞明白为什么。看了别人写的代码上有，加上，结果就过了==
知道了。感谢zj学长。
等号右边如果是int，左边是LL，超int了也会越界
就是说c=a*b 如果a 和b 是int C是long long 如果a*b超过了Int,就会越界...
需要先把两个int类型转化成long long 写成c=long long (a)*long long (b);
/******************************************************************* Author :111qqz *******************************************************************/ #include <algorithm> #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <map> #include <stack> #include <queue> #include <set> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int inf = 0x7fffffff; const int N=1E5+3; int T,n; int mu[N],a[N]; LL mul[N],p[N],sumt[N]; void getmu() { for (int i = 1 ; i <N ; i++) { int target = i ==1?1:0; int delta = target - mu[i]; mu[i] = delta; for ( int j = i+i; j <N ; j=j+i) mu[j] = mu[j] + delta; } } int main() { cin>>T; getmu(); while (T--) { cin>>n; // cout<<mu[n]<<endl; memset(p,0,sizeof(p)); memset(sumt,0,sizeof(sumt)); memset(mul,0,sizeof(mul)); memset(a,0,sizeof(a)); for ( int i = 0 ; i < n ; i++ ) { scanf("%d",&a[i]); sumt[a[i]]++; } for ( int i = 1 ; i < N ; i++) for ( int j = i ; j < N ; j=j+i) { mul[i] = mul[i] + sumt[j]; } for ( int i = 1 ; i < N ; i++ ) for ( int j = i ; j < N ; j=j+i) { p[j] = p[j] + mul[i]*mu[i]; } // p[1]--;//减到1和1本身互质的那个...因为题目中说所有人的id不相同了 // cout<<"p[1]:"<<p[1]<<endl; // for ( int i = 0 ; i < n ; i++) // cout<<"p[i]："<<a[i]<<" "<<p[a[i]]<<endl; LL ans=(LL)n*(n-1)*(n-2)/6; LL sum=0; for (int i=0;i<n;i++) { if (a[i]==1) continue; sum+=(LL)p[a[i]]*(LL)(n-1-p[a[i]]); } sum =(LL)sum/2; ans =(LL)(ans-sum); cout<<ans<<endl; } return 0; }