M - Weird Ceiling 【CCPC2024哈尔滨站】
M - Weird Ceiling
思路:
注意到
f
(
n
,
i
)
f(n,i)
f(n,i) 的值为
n
y
(
i
)
\frac{n} {y(i)}
y(i)n ，其中
y
(
i
)
y(i)
y(i) 为
n
n
n 小于等于
i
i
i 的最大因数。
那么先找到
n
n
n的所有因数，包括
1
1
1和它本身，在数组a[]中升序排列,数组长度为
l
e
n
len
len。
则
n
/
y
(
i
)
=
a
[
l
e
n
−
j
]
{n} / {y(i)}=a[len-j]
n/y(i)=a[len−j] ，
j
j
j为
y
(
i
)
y(i)
y(i)在a[]中的位置(从0开始)。
∑
i
=
1
n
f
(
n
,
i
)
=
∑
i
=
1
n
n
/
y
(
i
)
=
∑
j
=
1
l
e
n
−
1
a
[
l
e
n
−
j
]
×
(
a
[
j
]
−
a
[
j
−
1
]
)
+
1
\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
i=1∑nf(n,i)=i=1∑nn/y(i)=j=1∑len−1a[len−j]×(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;
}
原文地址：https://blog.csdn.net/2303_79310336/article/details/143575917
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！