问题
有一张 \(N\times N\) 的数表（\(N=10^5\)），其第 \(i\) 行第 \(j\) 列（\(1\le i\le n\)，\(1\le j\le m\)）的数值为能同时整除 \(i\) 和 \(j\) 的所有自然数之和。
有T次询问，每次询问给定 \(n,m,A\)，计算数表（1，1）至（n，m）中不大于 \(A\) 的数之和（\(|A|\le 10^9\)）。
每组数据输出一行一个整数，表示答案模 \(2^{31}\) 的值。
题解
| \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j)) \lbrack f(\gcd(i,j)) \leq A \rbrack\) \(f(x)\)表示 \(x\) 所有约数和。 |
|
|---|---|
| 假设先忽略条件 \(\lbrack f(\gcd(i,j)) \leq A \rbrack\) 的限制 设 \(n \leq m\) |
|
| \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j))\) | 111 |
| \(=\sum\limits_{d=1}^n \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} f(d)\lbrack\gcd(i,j)=1\rbrack\) | 222 |
| \(=\sum\limits_{d=1}^n f(d）\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\sum\limits_{a|\gcd(i,j)}\mu(a)\) | 333 |
| \(=\sum\limits_{d=1}^n f(d) \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\sum\limits_{a=1}^{\frac{n}{d}} \lbrack a|i \rbrack \lbrack a|j \rbrack \mu(a)\) | 444 |
| \(=\sum\limits_{d=1}^n f(d) \sum\limits_{a=1}^{\frac{n}{d}}\mu(x)\sum\limits_{i=1}^{\frac{n}{d}}\lbrack a|i \rbrack\sum\limits_{j=1}^{\frac{m}{d}}\lbrack a|j \rbrack\) | 555 |
| \(=\sum\limits_{d=1}^n f(d) \sum\limits_{a=1}^{\frac{n}{d}}\mu(a)\lfloor\frac{n}{ad}\rfloor\lfloor\frac{n}{ad}\rfloor\) | 666注：到此为止，如果不进一步优化，结果50分超时。 |
| 设 \(T=ad\) | 777 |
| \(=\sum\limits_{d=1}^n f(d) \sum\limits_{\frac{T}{d}=1}^{\frac{n}{d}}\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor\lfloor \frac{n}{T} \rfloor\) | 888 |
| \(=\sum\limits_{d=1}^n f(d) \sum\limits_{T=1}^n\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor\) | 999 |
| \(=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor \sum\limits_{d|T}f(d) \mu(\frac{T}{d})\) | 设 \(F(T)=\sum\limits_{d|T}f(d) \mu(\frac{T}{d})\) ，可以前缀和 发现当 \(f(d) \leq A\)时才会对 \(F(T)\) 做贡献。于是我们将询问按\(A\)从小到大排序，枚举询问的时候，\(A\)变大会使得一些f(d)对F(T)产生贡献，我们就用枚举倍数的方法来找到所有的T，然后我们需要动态修改F(T)的值，而且还要支持区间询问，因此我们使用常数较小的树状数组实现 初始化代码如下： F[0]=0;for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)F[j]+=mu[j/i]*f[i]; |
| \(=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{n}{T} \rfloor F(T)\) |
具体代码如下：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e6;
int pr, p[N+10];LL mu[N+10],F[N+10];bool v[N+10];
void init()
{
memset(v, 0, sizeof(v));
pr=0;mu[0]=0;mu[1]=1;
for(int i=2;i<=N;i++)
{
if(!v[i]) p[++pr]=i, mu[i]=-1;
for(int j=1;j<=pr&&p[j]*i<=N;j++)
{
v[i*p[j]]=true;
if(i%p[j]==0) {mu[i*p[j]]=0; break;}
mu[i*p[j]]=-mu[i];
}
}
F[0]=0;
for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)
F[j]+=mu[j/i]*i;
for(int i=1;i<=N;i++)F[i]+=F[i-1];
}
LL calc(LL n)
{
LL ans=0;
for(LL l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(F[r]-F[l-1])*(n/l)*(n/l);
}
return ans;
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
LL n;scanf("%lld",&n);
printf("%lld\n",calc(n));
}
return 0;
}