Code HDU - 5212[Mobius]

题意:

给定长为n的数组A, a[i]<=1e4

思路:有如下定义

f(n)为gcd==n的对数

F(n)为gcd是n倍数的对数

Accepted 5212 124MS 1624K 1483B G++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+4;
const ll MOD=10007;
const ll Seed=2333;

int mu[N], vis[N], prime[N];
int summu[N];
int tot;//用来记录prime的个数
void init(){
    mu[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!vis[i]){
            prime[tot ++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j ++){
            vis[i * prime[j]] = 1;
            if(i % prime[j]) mu[i * prime[j]] = -mu[i];
            else{
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}
void adjust(ll &a){
    a%=MOD;
    a+=MOD;
    a%=MOD;
}
ll a[N],F[N];
int main(void){
    init();
    int n;
    while(scanf("%d",&n)==1){
        ll mx=0;
        for(int i=1;i<=n;i++)   scanf("%lld",&a[i]),mx=max(mx,a[i]);
        ll ans=0;
        memset(F,0,sizeof F);
        for(int i=1;i<=n;i++){
            for(int j=1;j*j<=a[i];j++){
                if(a[i]%j==0){
                    F[j]++;
                    if(j*j==a[i])   continue;
                    else    F[a[i]/j]++;
                }
            }
        }
        for(int i=1;i<=mx;i++)  F[i]=F[i]*F[i];
        for(ll d=2;d<=mx;d++){
            ll f=0;
            for(ll dd=d;dd<=mx;dd+=d)   f+=mu[dd/d]*F[dd];
            ans+=f*d*(d-1);
            adjust(ans);
        }
        printf("%lld\n",ans);
    }

    return 0;
}