hust 2015夏休み合宿

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82839#problem/C
14年鞍山地区の試合のテーマは…
その時は満場で4番目の問題だったと記憶していますが…
話をする時、麗潔姉さんは「莫比烏斯反演blablabla」と言いました.
全然分かりませんでした.
えっと、初めてモビル反転というものに触れました.これは数論で重要なようです.
この問題で注意したいのは、xとの互質の個数を求める時、1とどの正の整数も互いに質的なものですが、1と1の互質はこの組は条件に合わないです.判断してください.
Mobius関数を求めて、ふるいがあるようです.(賈志鵬の線形ふるい.pdfを見てください.)そして赤い本には1~nのmobius関数の値を求める方法があります.
そして強制的に変換されたタイプが2発のWAをピットしました.long longを開くには、強制変換を書かないとWAになります.なぜかまだ分かりません.他の人が書いているコードを見たらあります.加えて、結果は過ぎました.
分かりました.zj先輩、ありがとうございます. 
 等号の右側がintなら、左がLLです.超intもアウトします. 
つまりc=a*bです aとbがintなら Cはlong longです a*bがIntを超えたら、オフラインに…
まず二つのintタイプをlong 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;

}