题意
给定长度为 $n$ 的数组，求：
$$\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=i}^n \gcd\left\{a_i, a_{i + 1}, \ldots, a_j\right\}$$
对 $998244353$ 取模。
题解
对于这个问题，$\gcd$ 是单调递减的，因此可以使用 ST 来维护区间 $\gcd$，统计答案时对于每个 $\gcd$ 值，乘以对应区间长度即可。
显然这不够难！
考虑加强一下：
$$\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=i}^n \gcd\left\{a_i, a_{i + 1}, \ldots, a_j\right\} \cdot \max\left\{a_i, a_{i + 1}, \ldots, a_j\right\}$$
好的，发现原题了 https://www.luogu.com.cn/problem/P9607
题解
还是很简单，在一段区间里，最大值是不会改变的。所以对于每个最大值，乘上对应 $\gcd$ 值和长度，就是这个值的贡献。线段树维护最大值即可。
代码
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// Only one ace left.
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define _CONSOLE 0
// #define EFILE ""
using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;
template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
_Type& operator[](size_t index) { return this->at(index); }
};
// Defines
// Constants
constexpr tp Hat_N = 5e5, mod = 998244353;
// Classes
struct Seg_Tree {
mray<tp, Hat_N * 4> laz;
mray<tp, Hat_N * 4> val;
void push(tp x) { val[x] = (val[x << 1] + val[x << 1 | 1]) % mod; }
void pull(tp x, tp l, tp r) {
if (laz[x]) {
tp mid = l + r >> 1;
laz[x << 1] = laz[x << 1 | 1] = laz[x];
val[x << 1] = laz[x] * (mid - l + 1) % mod;
val[x << 1 | 1] = laz[x] * (r - mid) % mod;
laz[x] = 0;
}
}
void build(tp x, tp l, tp r) {
tp mid = l + r >> 1;
laz[x] = val[x] = 0;
if (l == r) return;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
push(x);
}
void modify(tp x, tp l, tp r, tp ml, tp mr, tp k) {
if (l <= ml && mr <= r) {
val[x] = k * (mr - ml + 1);
laz[x] = k;
} else {
tp mid = ml + mr >> 1;
pull(x, ml, mr);
if (l <= mid) modify(x << 1, l, r, ml, mid, k);
if (r > mid) modify(x << 1 | 1, l, r, mid + 1, mr, k);
push(x);
}
}
tp query(tp x, tp l, tp r, tp ml, tp mr) {
if (l <= ml && mr <= r) return val[x];
else {
tp mid = ml + mr >> 1, ans = 0;
pull(x, ml, mr);
if (l <= mid) ans += query(x << 1, l, r, ml, mid);
if (r > mid) ans += query(x << 1 | 1, l, r, mid + 1, mr);
return ans % mod;
}
}
} tre;
// Typedeves
// Variables
tp n, ans;
// Arrays
stack<tp> stk;
mray<tp, Hat_N> lg, pmav;
mray<mray<tp, 17>, Hat_N> st;
// Functions
void MIST() {
}
// :/
tp gcd(tp a, tp b) { return !b ? a : gcd(b, a % b); }
void STP() {
tp k = log2(n / 2) + 1;
lg[1] = 0;
for (tp i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for (tp j = 1; j <= k; ++j) {
for (tp i = 1; i + (1ll << j) - 1 <= n; ++i) st[i][j] = gcd(st[i][j - 1], st[i + (1ll << j - 1)][j - 1]);
}
}
tp sgcd(tp l, tp r) {
tp k = lg[r - l + 1];
return gcd(st[l][k], st[r - (1ll << k) + 1][k]);
}
void calc(tp x, tp h) {
if (x <= 0) return;
tp l = 1, r = x - 1, g = sgcd(x, h);
while (l <= r) {
tp mid = l + r >> 1;
if(sgcd(mid, h) == g) r = mid - 1;
else l = mid + 1;
}
ans = (ans + tre.query(1, l, x, 1, n) * g) % mod;
calc(l - 1, h);
}
void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
cin >> n;
tre.build(1, 1, n);
for (tp i = 1; i <= n; ++i) cin >> st[i][0];
for (tp i = 1; i <= n; ++i) {
while (stk.size() && st[stk.top()][0] < st[i][0]) stk.pop();
pmav[i] = stk.empty() ? 1 : stk.top() + 1;
stk.push(i);
}
STP();
for (tp i = 1; i <= n; ++i) {
tre.modify(1, pmav[i], i, 1, n, st[i][0]);
calc(i, i);
}
cout << ans << '\n';
}
#include <fstream>
signed main() {
tp t = 0, _t = 1;
cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
static ifstream _in("input.in");
cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
static ifstream _in(EFILE ".in");
static ofstream _out(EFILE ".out");
cin.rdbuf(_in.rdbuf());
cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
// cin >> _t;
MIST();
while (t < _t) STRUGGLING(++t);
return 0;
}
//*/显然这还是不够难！
送你一道难题吧。
定义对正整数 $x$ 的一次变换为：在集合 $\{-1, 1\}$ 中等概率随机一个变量 $k$，让 $x$ 变为变为 $x + k \cdot \operatorname{lowbit}\left(x\right)$。
定义 $f\left(x\right)$ 表示正整数 $x$ 变换为 $0$ 的期望步数。如果期望步数不是整数，设期望步数的最简分数为 $\frac pq$，则以 $p \cdot q^{-1}$ 表示。其中 $q^{-1}$ 表示 $q$ 在取模意义下的逆元。
求 $\displaystyle\sum\limits_{i=l}^r f\left(i\right)$
答案对 $998244353$ 取模。
$l \leq r \leq 10^{18}$