题给代码可以转化为下面的公式

然后用F[n]记录公约数为n的(a[i],a[j])对数，用f[n]记录最大公约数为n的(a[i],a[j])对数

之后枚举最大公约数d

至于求F[n]，可以先将1~10000全部因数分解，用num[i]记录约数中包含i的a[x]的个数。对每一个a[i]，其每一个约数都对对应的num[i]贡献了1 。显然，F[n]=num[n]*num[n]

#include
     
      using namespace std;typedef long long LL;const int mod=10007;const int maxn=1e6;int prime[maxn+5];bool check[maxn+5];int mu[maxn+5];void init(){    mu[1]=1;    int tot=0;    for(int i=2;i<=maxn;i++)    {        if(!check[i])        {            prime[tot++]=i;            mu[i]=-1;        }        for(int j=0;j
      
       maxn) break;            check[i*prime[j]]=true;            if(i%prime[j]==0)            {                mu[i*prime[j]]=0;                break;            }            else            {                mu[i*prime[j]]=-mu[i];            }        }    }}int n;int a[10005];LL num[10005];vector
       
         fac[10005];LL f[10005];LL F[10005];void init1(){    for(int i=1;i<=10000;i++)    {        int j;        for(j=1;j*j