M - Weird Ceiling

思路:

注意到 $f(n,i)$ 的值为 $\frac{n}{y(i)}$ ，其中 $y(i)$ 为 $n$ 小于等于 $i$ 的最大因数。
那么先找到$n$的所有因数，包括$1$和它本身，在数组a[]中升序排列,数组长度为$len$。
则$n/y(i)=a[len-j]$ ，$j$为$y(i)$在a[]中的位置(从0开始)。
$$\sum _{i=1}^{n}f(n,i)=\sum _{i=1}^{n}n/y(i)=\sum _{j=1}^{len-1}a[len-j]\times (a[j]-a[j-1])+1$$

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;void solve() {int n;cin>>n;vector<int> a;for(int i=1;i<=sqrt(n);i++){if(n%i==0){a.push_back(i);a.push_back(n/i);}}sort(a.begin(),a.end());int ans = 1; //1是f(n,n)的值int len = a.size();for(int i=1;i<len;i++){ans+= a[len-i]*(a[i]-a[i-1]);}cout<<ans<<endl;
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}