HDU 5212

Description:

给定一个数列 ,然后求
$$Ans=\sum_{i=1}^{N}\sum_{j=1}^{N}gcd(a_i,a_j)*(gcd(a_i,a_j)-1)~Mod~10007~~(1<=a_i,N<=10000)$$



Solution:

首先我们令 表示 这个数字在数列 中出现的次数。

那么

我们 ,并且构造函数 使得

所以

最终
$$Ans=\sum_{d=1}^{10000}fr(d)(\sum_{i=1}^{\left \lfloor \frac{10000}{d}\right \rfloor}num[i*d])^2$$

怎么求?直接根据前面的定义式莫比乌斯反演就行了。

Code:

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

using namespace std;

const int Mod=10007;

int N;
int a[10010]={0};
int F[10010]={0};
int fr[10010]={0};

int main()
{
    for(int i=1;i<=10000;i++)
    {
        fr[i]=(fr[i]+i*(i-1)%Mod)%Mod;
        for(int j=i+i;j<=10000;j+=i)
            fr[j]=(fr[j]+Mod-fr[i])%Mod;
    }
    for(;scanf("%d",&N)!=EOF;)
    {
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
            F[a[i]]++;
        }
        int ans=0;
        for(int d=1;d<=10000;d++)
        {
            int sum=0;
            for(int i=10000/d;i>=1;i--)
                sum=(sum+F[i*d])%Mod;
            ans=(ans+sum*sum%Mod*fr[d])%Mod;
        }
        printf("%d\n",ans);
        memset(F+1,0,sizeof(int)*10000);
    }
    return 0;
}