Acdream 1117 Number theory(モビウス反転)

タイトルリンク:
http://acdream.info/problem?pid=1114
 
タイトル:
シーケンスを与え、シーケンス内の相互質の数の対数を求める.
 
分析:
f(d)はgcdがちょうどdの数である個数を表し,F(d)はgcdがdの倍数である個数を表す
従って、F(d)=sigma(f(n))  (n%d==0)
            f(n)= sigma( mu[d]*F[n/d] ) (n%d==0);
そこで、まず各数に現れる周波数numを統計します.
そして、iの倍数の個数をcnt[i]で表す.
F(i) = C(cnt[i],2);
私たちが最終的に要求した結果はf(1)である.
コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define DWN(i,h,l) for(int i=(h);i>=(l);--i)
#define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v))
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
#define PI acos(-1.0)
#define INF 1000000000
#define LINF 1000000000000000000LL
#define eps 1e-8
#define maxn  222223
#define LL long long
using namespace std;

int mu[maxn];
int a[maxn];
bool vis[maxn];
int num[maxn];
int cnt[maxn];
int prime[maxn];
void mobi(){
    int cnt = 0 ;
    CLR(vis);
    mu[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];//i prime[j]    mu[i*prime[j]]    mu[i]           
            else{
                mu[i*prime[j]]==0;//       prime[j]
                break;
            }
        }
    }
}

int main()
{
    mobi();
    int n;
    while(~scanf("%d",&n)){
        int mmax = -1;
        CLR(cnt);
        CLR(num);
        REP(i,n){
            scanf("%d",a+i);
            mmax = max(a[i],mmax);
        }
        REP(i,n) num[a[i]]++;
        FOR(i,1,mmax){
            IFOR(j,i,mmax,i){
                cnt[i]+=num[j];
            }
        }
        LL ans = 0;
        FOR(i,1,mmax)
        ans +=mu[i]*(LL)cnt[i]*(cnt[i]-1)/2;
        printf("%lld
",ans);
    }
    return 0;
}