题目链接
题目大意
给了你一个函数 \(f(a,b)\)，让你求 \(\sum_{i=1}^a f(a,i)\) 的值。
Solution
首先我们来看 \(f(a,b)\) 到底是求得啥，其实把伪代码翻译成过来其实就是让 \(b\) 一直递减，直至减到能被 \(a\) 整除，返回 \(a/b\) 的值。
能被 \(a\) 整除的肯定是 \(a\) 的约数了，所以 \(f(a,b)\) 返回的值其实就是 \(a\) 除以 \(\le b\) 的最大约数的值。题目让我们求 \(\sum_{i=1}^a f(a,i)\)，我们可以发现，\(a\) 的一个约数到另一个约数之间的 \(f(a,i)\) 的值都是 \(a\) 除以前一个约数的值，然后我们就发现 \(a\) 的每一个约数间隔中 \(f(a,i)\) 的加和其实就是这段间隔的距离乘上 \(a\) 除以这段间隔前面的那一个约数。
然后我们可以先把 \(a\) 的约数处理出来，然后把每段间隔的贡献加起来。比如样例中 \(a=114514\) 的情况（图画得有点丑，请见谅）：
图中每条线代表着每个间隔与其对应的 \(a\) 除这段间隔前一个约数的值相乘，但是我们发现与样例结果少 \(1\)，那是因为这张图中只把间隔算了进去，相当于是算了 \(a-1\) 个数，最后一个当 \(i=a\) 的情况没算，而 \(i=a\) 时正好是自己除以自己，所以结果应该 \(+1\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int T=read(),f[N];
signed main(){while(T--){int n=read(),ans=0,cnt=0;for(int i=1;i*i<=n;i++){//处理约数 if(n%i==0){f[++cnt]=i;if(i!=n/i)f[++cnt]=n/i;}}sort(f+1,f+cnt+1);//这里要排个序，因为上边找约数时是对半找的 for(int i=2,j=cnt;i<=cnt,j>=2;i++,j--)ans+=(f[i]-f[i-1])*f[j];//统计每一段间隔内的答案 ans++;printf("%lld\n",ans);}return 0;
}