给出 \(n\),对于任意正整数 \(i\) 满足 \(1 \leq i \leq n\),求有多少个正整数 \(j\) 满足 \(1\ leq j \leq n\) 且 \(i \bmod j \leq \frac{j}{2}\)。
枚举 \(i\) 不好处理,可以反过来,外层枚举 \(j\),内层枚举左右端点 \(l = kj,r = kj + \lfloor \frac{j}{2} \rfloor\)(\(k\) 为自然数且 \(kj \leq n\)),可知 \(ans_l,ans_{l + 1},\cdots,ans_{r}\) 均要加 \(1\),这可以用差分实现。
复杂度 \(O(n \log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 9;
int n;
int ans[N << 1];//这里需要稍微开大一点
signed main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int j = 1;j <= n;j++)
for(int i = 0;i <= n;i += j){
ans[i]++;
ans[i + (j - 1 >> 1) + 1]--;
}
for(int i = 1;i <= n;i++){
ans[i] += ans[i - 1];
cout << ans[i] << ' ';
}
return 0;
}
标签:四舍五入,10,int,kj,31,leq,枚举,ans
From: https://www.cnblogs.com/5002-qwq/p/18517579