让你求一个关于 $n$ 的等式，$\bmod 10^9+7$。
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^i\gcd(j,i\oplus j)^k
\\=&\sum_{j=1}^n\sum_{i=j}^n\gcd(j,i\oplus j)^k
\\=&\sum_{j=1}^n\sum_{k=0}^N\gcd(j,k)\cdot[j\leqslant j\oplus k\leqslant n]
\end{aligned}
$$
注意到对于每一个 $j$，其内部 $[j \leqslant j \oplus k \leqslant n]$ 连续的 $1$ 构成 $\log n$ 段，因为可以转换为 $[j\oplus k\leqslant n]-[j\oplus k<j]$，这两个式子从 Trie 树上考虑就是有 $w=32$ 种情况（每一位比大小），每种情况都是连续的一段。
所以原问题转化为 $\displaystyle \sum_{j=1}^n\sum_{l,r}\sum_{x=l}^r\gcd(j,x)^k$ 其中每层 $j$ 的 $l,r$ 枚举不超过 $\log n$ 次。而后面的显然可以差分，然后套莫反。
$$
\begin{aligned}
&\sum_{i=1}^m\gcd(i,j)^K
\\=&\sum_{d=1}^md^K\sum_{i=1}^n[\gcd(i,j)=d]
\\=&\sum_{d=1}^md^K\sum_{i=1}^n[d | \gcd(i,j)]\sum_{k|\frac{\gcd(i,j)}{d}}\mu(k) \qquad &注意到只有\,d|\gcd(i,j)\, 时才有贡献
\\=&\sum_{d|j}d^K\sum_{d|i}\sum_{k|\frac i d \land k|\frac j d}\mu(k) \qquad &将\,k\,枚举提到前面
\\=&\sum_{k|j}\mu(k)\sum_{d|\frac j k}d^K\sum_{k\cdot d|i} 1
\\=&\sum_{k|j}\mu(k)\sum_{d|\frac j k}d^K\lfloor \frac{n}{k\cdot d} \rfloor
\\=&\sum_{kd|j}\lfloor \frac{m}{kd} \rfloor \sum_{k|kd}\mu(k)\cdot (\frac{kd}{k})^K \qquad &把\,k\cdot d\,提到前面枚举，后面就能预处理
\end{aligned}
$$
所以这个式子可以分布处理，先预处理后面那个卷积，然后再暴力计算即可。总的时间复杂度 $\mathcal O(n\log n \ln n)$。
现在讲一下如何处理那个异或小于不等式。
考虑从大到小枚举位数 $d$，如果有 $ a \oplus x \leqslant b $，对于位数 $d’>d$ 左边$=$右边，在 $d$ 上左边是 $0$ 右边是 $1$，那后面的 $d’<d$ 左边就随便选了。
$$
\begin{aligned}
&\tt{aaaaaaaaaaaaa} \\
\oplus\quad&\tt{xxxxxxxxxxxxx} \\
\hline
=\quad&\tt{yyyyyy{\color{red}0}yyyyyy} \\
\leqslant\quad&\tt{bbbbbb{\color{red}1}bbbbbb} \\
& (\text{cur }d=6)
\end{aligned}
\to
\begin{aligned}
&\text{When } d=5,4,\dots 0 \\
&x\text{ chooses arbitrarily}
\end{aligned}
$$
所以最多可能会有 $\log$ 级别的整段区间。
最后别忘了这题存在 $\gcd(x,0)=x$ 条件。被这个曹飞了