给你 \(L\le 10^6\)，\(x,y\le 100\)，要求 \(\sum _{lcm(a,b)\le L} \left| ax-by \right|\)。
喜闻乐见的推式子：
\[\begin{aligned} &\sum _{lcm(a,b)\le L} \left| ax-by \right|\\ &=\sum _{d=1}^L d \sum _{a=1}^{\lfloor\frac{L}{d}\rfloor} \sum _{b=1}^{\lfloor\frac{L}{da}\rfloor} [\gcd(i,j)=1]\left|ax-by\right|（d是a和b的\gcd） \\ &=\sum _{d=1}^L d \sum _{a=1}^{\lfloor\frac{L}{d}\rfloor} \sum _{b=1}^{\lfloor\frac{L}{da}\rfloor} \sum_{u|i,u|j}\mu(u)\left|ax-by\right|（莫反） \\ &=\sum _{d=1}^L d \sum _{u=1}^{\lfloor\frac{L}{d}\rfloor} \mu(u)u \sum _{a=1}^{\lfloor\frac{L}{du^2}\rfloor} \sum _{b=1}^{\lfloor\frac{L}{du^2a}\rfloor} \left|ax-by\right|（改变枚举顺序） \\ &=\sum _{T=1}^L \sum _{u^2|T} \mu(u)u\frac{T}{u^2} \sum _{a=1}^{\lfloor\frac{L}{T}\rfloor} \sum _{b=1}^{\lfloor\frac{L}{Ta}\rfloor} \left|ax-by\right|（令T=du^2）\\ &=\sum _{T=1}^L (\sum _{u^2|T} \mu(u)\frac{T}{u}) (\sum _{a=1}^{\lfloor\frac{L}{T}\rfloor} \sum _{b=1}^{\lfloor\frac{L}{Ta}\rfloor} \left|ax-by\right|)（整理） \end{aligned} \]其中，对于每一个 \(T\)，前一个括号可以通过一开始从小到大枚举 \(u\) 贡献到 \(T\) 预处理出来，时间复杂度 \(\sum_{u=1}^L O(\frac{n}{i^2})<O(n\ln n)\)；后一个括号相当于求 \(\sum_{T=1}^L w_Tf(\frac{L}{T})\)，其中 \(f(n)=\sum_{i=1}^{n}\sum_{j=1}{\frac{n}{i}}\left|ix-jy\right|\)，\(w\) 是第一个括号，可以用整除分块做，大概是 \(O(n\ln n)\)，但是跑得很快。
点击开 D
const int N=1e6+99;
ll L,x,y,xi[N]={};
int mu[N]={},su[N]={}; bool flag[N]={};
ll f(int n) {
int i,j,top; ll ans=0;
for(i=1;i<=n;++i)
for(j=1,top=n/i;j<=top;++j)
ans+=abs(i*x-j*y);
return ans;
}
int main()
{
usefile("a");
ll ans=0,i,j,l,r;
read(L,x,y);
flag[1]=true,mu[1]=1;
for(i=2;i<=L;++i) {
if(!flag[i]) su[++su[0]]=i,mu[i]=-1;
for(j=1;j<=su[0]&&i*su[j]<=L;++j) {
flag[i*su[j]]=true;
if(i%su[j]==0) {
mu[i*su[j]]=0; break;
} else mu[i*su[j]]=-mu[i];
}
}
for(i=1;i<=L;++i)
if(mu[i])
for(j=i*i;j<=L;j+=i*i)
xi[j]+=mu[i]*j/i;
for(i=1;i<=L;++i) xi[i]+=xi[i-1];
for(l=1;l<=L;l=r+1)
r=L/(L/l),ans+=(xi[r]-xi[l-1])*f(L/l);
printf("%lld\n",ans);
return 0;
}