题解：P14813 [CCPC 2024 哈尔滨站] 奇怪的上取整
zhoumurui
·
·
题解
题面展示
多次询问，每次问 $\sum_{i=1}^{n}f(n,i)$。
### 解题思路
在洛谷 VP 的本场比赛。这里展示赛时写法。
众所周知，当 $i$ 取不大于 $n$ 的正整数时，$\lfloor\frac{n}{i}\rfloor$ 的取值总数不超过 $O(\sqrt n)$ 个。
合理怀疑换成向上取整也同样适用。
实际上，当我们把向下取整换成向上取整时，当且仅当 $i$ 是 $n$ 的因子时结果不变，否则结果会加上 $1$。
数论分块处理到一个区间 $[l,r]$ 时，由于这个区间都满足 $\lfloor\frac{n}{i}\rfloor$ 相等且 $\frac{n}{i}$ 递减，所以只有 $r$ 可能是 $n$ 的因数。
因此进行数论分块并特判 $r$ 即可。
如何快速计算 $f(a,b)$。
注意到数论分块处理的过程中 $b$ 是递增的，所以 $\frac{a}{b}$ 是递减的。
预处理出 $n$ 的所有因子，然后在数论分块处理的时候双指针即可。
总复杂度 $O(T\sqrt n)$。
写了一份之后，发现跑了 2s，拼尽全力卡常**卡了两个小时**卡到 1.02s 然后就卡不动了。
考虑到数论分块的常数很大，将前 $\sqrt n$ 项剥出来单独处理，这样常数几乎少了一半就通过了。
### 代码展示
由于这份代码辗转与我和队友的电脑上（轮流卡常），因此码风比较混乱。
当然后来发现不用卡。
```cpp
#include <bits/extc++.h>
using namespace std;
namespace hd {
const int mod = 998244353;
struct modint {
int val;
modint() { val = 0; }
modint(int _v) { val = _v; }
friend modint operator+(const modint &a, const modint &b) {
modint res;
res.val = a.val + b.val;
res.val = res.val >= mod ? res.val - mod : res.val;
return res;
}
friend modint operator*(const modint &a, const modint &b) {
modint res;
res.val = 1ll * a.val * b.val % mod;
return res;
}
void operator+=(const modint &a) {
val += a.val;
val = val >= mod ? val - mod : val;
}
void operator*=(const modint &a) { val = 1ll * val * a.val % mod; }
friend modint operator-(const modint &a, const modint &b) {
modint res;
res.val = a.val - b.val;
res.val = res.val < 0 ? res.val + mod : res.val;
return res;
}
void operator-=(const modint &a) {
val -= a.val;
val = val < 0 ? val + mod : val;
}
modint inv() {
modint a = val;
int b = mod - 2;
modint res = 1;
while (b) {
if (b & 1) {
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
friend modint pow(modint a, int b) {
modint res = 1;
while (b) {
if (b & 1) {
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
};
struct FSI {
template <typename T>
friend FSI &operator>>(FSI &in, T &res) {
res = 0;
T f = 1;
char ch = getchar();
while (!isdigit(ch) && ch != EOF) {
if (ch == '-') f = -1;
ch = getchar();
}
if (ch == EOF) {
res = 0;
return in;
}
while (isdigit(ch) && ch != EOF) {
res = (res * 10) + (ch - 48);
ch = getchar();
}
res *= f;
return in;
}
};
template <>
FSI &operator>>(FSI &in, string &res) {
res.clear();
char ch = getchar();
while ((isblank(ch) || ch == '\n') && ch != EOF) {
ch = getchar();
}
if (ch == EOF) {
res = "";
return in;
}
while (!isblank(ch) && ch != '\n' && ch != EOF) {
res.push_back(ch);
ch = getchar();
}
return in;
}
static FSI sr;
struct FSO {
template <typename T>
friend FSO &operator<<(FSO &out, T res) {
static std::streambuf *outbuf = cout.rdbuf();
static char stack[110];
static int top = 0;
if (res < 0) {
outbuf->sputc('-');
res = -res;
}
if (!res) {
outbuf->sputc('0');
return out;
}
while (res) {
stack[++top] = res % 10 + '0';
res /= 10;
}
while (top) {
outbuf->sputc(stack[top]);
--top;
}
return out;
}
};
template <>
FSO &operator<<(FSO &in, string res) {
static std::streambuf *outbuf = cout.rdbuf();
outbuf->sputn(res.c_str(), res.size());
return in;
}
template <>
FSO &operator<<(FSO &in, const char *res) {
static std::streambuf *outbuf = cout.rdbuf();
outbuf->sputn(res, strlen(res));
return in;
}
template <>
FSO &operator<<(FSO &in, modint res) {
static std::streambuf *outbuf = cout.rdbuf();
in << res.val;
return in;
}
static FSO sw;
static bool flag = false;
void inter(bool f = true) { flag = f; }
struct FSE {
friend FSO &operator<<(FSO &out, FSE &in) {
static std::streambuf *outbuf = cout.rdbuf();
outbuf->sputc('\n');
if (flag) {
cout.flush();
}
return out;
}
};
static FSE sendl;
FSO &endl(FSO &in) {
in << sendl;
return in;
}
FSO &operator<<(FSO &in, FSO &(*f)(FSO &)) { return f(in); }
} // namespace hd
using i64 = long long;
using namespace hd;
int n;
int f[1000005],cnt,i,l,r,p;
long long ans;
void solve() {
sr >> n;
cnt=ans=0;
for (i = 1; i * i <= n; ++i) {
if (n % i == 0) {
f[++cnt] = i;
ans+=n/i;
}
else ans+=n/f[cnt];
}
l=i;
for (i = cnt - (f[cnt] * f[cnt] == n); i >= 1; i--) {
f[++cnt] = n / f[i];
}
while (l<=n){
r=n/(n/l);
while (f[cnt - 1] >= n/l + 1) --cnt;
ans += (long long)(r - l) * f[cnt];
if (f[cnt - 1] >= n/l && r*(n/l)==n) --cnt;
ans += f[cnt];
l=r+1;
}
sw << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0);
// int st = clock();
int t;
sr >> t;
while (t--) solve();
// int ed = clock();
// cout << "Time: " << 1.0 * (ed - st) / CLOCKS_PER_SEC << "s\n";
return 0;
}
```