题目概述

一个整点 $(x,y)$ 的代价 $w(x,y)$ 是与 $(0,0)$ 连线上的整点的个数的两倍减三，求 $\sum_{i=1}^{n}\sum_{j=1}^{m}w(i,j)$ 。

解题报告

快烂掉的结论：连线上整点的个数是 $gcd(x,y)+1$ 。那么就是求

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}2(i,j)-1=[2\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)]-nm $$

来推一推：

$$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)&=\sum_{d=1}^{min\{n,m\}}\sum_{d|i}\sum_{d|j}d\cdot[({i\over d},{j\over d})=1]\\ &=\sum_{d=1}^{min\{n,m\}}\sum_{i=1}^{\lfloor{n\over d}\rfloor}\sum_{j=1}^{\lfloor{m\over d}\rfloor}d\cdot e[(i,j)]\\ &=\sum_{d=1}^{min\{n,m\}}d\sum_{i=1}^{\lfloor{n\over d}\rfloor}\sum_{j=1}^{\lfloor{m\over d}\rfloor}\sum_{k|d}\mu(k)\\ &=\sum_{d=1}^{min\{n,m\}}d\sum_{k=1}^{min\{\lfloor{n\over d}\rfloor,\lfloor{m\over d}\rfloor\}}\mu(k)\lfloor{n\over dk}\rfloor\lfloor{m\over dk}\rfloor\\ &=\sum_{d=1}^{min\{n,m\}}d\sum_{d|T}\mu({T\over d})\lfloor{n\over T}\rfloor\lfloor{m\over T}\rfloor \end{aligned} $$

预处理 $\mu$ ，枚举 $d$ 和 $T$ 是调和级数，所以复杂度为 $O(nln(n))$ 。

好像还有高端做法是先搞出两个函数得到答案式子然后反演一下得到上面的答案式子，没有了解过……

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,m,u[maxn+5],p[maxn+5];bool pri[maxn+5];LL ans;

inline void Make(int n){
    pri[0]=pri[1]=true;u[1]=1;
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,u[i]=-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            if (i%p[j]) u[t]=u[i]*u[p[j]],pri[t]=true; else {u[t]=0;pri[t]=true;break;}
    }
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    Make(maxn);scanf("%d%d",&n,&m);
    for (int i=1;i<=n&&i<=m;i++)
        for (int j=i;j<=n&&j<=m;j+=i)
            ans+=(LL)i*u[j/i]*(n/j)*(m/j);
    return printf("%lld\n",ans*2-(LL)n*m),0;
}