自动搬运

查看原文

来自洛谷，原作者为

	liuliucy **

搬运于2025-08-24 22:47:59，当前版本为作者最后更新于2023-07-18 14:07:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题目看到数据都会以为是 $O(1)$ 复杂度的吧……

所以直接数学方法暴力求解。

1.求解答案

首先看题目，对于任意的 $n$，其三次方都能表示成 $n$ 个连续奇数的和。

令集合 $S_{n} =\left \{ x_{n}|f(x_{n})=n \right \}$，目标：求其中最小的元素 $x_{n,1}$ 的值。

由题目可得 $S$ 内所有元素的和等于 $n^3$，根据高斯求和公式：

$$\frac{(x_{n,1}+2(n-1))n}{2}=n^3$$

易解得: $x_{n,1}=n^2-n+1$。

因此可得最大元素：$x_{n,n}=n^2+n-1$。

设 $f(k)=p$，然后考虑分区间，将原来 $[1,k]$ 区间分成 $S_{1}+S_{2}+S_{3}+...+S_{p-1}+R$，$R$ 表示分区间后的剩余元素集合。

则答案为：

$$\sum_{i=1}^{p}\sum_{j=1}^{i} i+\sum_{i=x_{p,1}}^{k}p $$

化简一下：

$$=\sum_{i=1}^{p}i^2+\frac{k-x_{p,1}+2}{2}p$$ $$=\frac{(p-1)p(2p-1)}{6}+\frac{k-(p^2-p+1)+2}{2} p$$

再考虑求 $p$，先计算 $x_{n,1}=k$，也就是：

$$n^2-n+1=k$$

得：

$$n=\frac{\sqrt{4k-3} +1}{2}$$

显然：$x_{p,1} \le k < x_{p+1,1}$。

也就是：$x_{p,1} \le x_{n,1} < x_{p+1,1}$。

所以：$p=\left \lfloor n \right \rfloor$。

这样，我们就求出了这道题。

2.数据范围与取模

先注意数据范围，$k<2^{64}$，所以 $p<2^{32}$，注意我们上边的求解过程，计算出的答案最大是 $p^3$ 左右，大概为 $2^{96}$，我们可以用 __int128 储存变量，但是会因为常数过大超时，所以我们要在计算时先确定好能被除数整除的数，先对其做除法，便可以完美的求出答案。

但注意另外一个点，求 $p$ 的过程中，计算 $\sqrt{4k-3}$ 时会先计算 $4k-3$ 但是计算时电脑是使用 $64$ 位二进制储存的，但是 __int128 并不支持根号运算，所以在计算时要考虑强转 long double 再存入 $p$ 中，注意 $p$ 不能使用 __int128 储存，不然会导致常数过大导致超时。

取模也是一个问题，为了节省常数复杂度，不能暴力直接全用 __int128，所以当我们除以 $2$ 时，我们得考虑乘上它的乘法逆元，再考虑取余，显然 $2$ 此时的乘法逆元是 $500000004$ 所以我们取余时就可以分开取余了。

3.Code

展示我丑陋的代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull md=1e9+7;
const ull ppp=500000004;
namespace Mker {
	ull SA, SB, SC, p = -1;
	int base;
	void init(){scanf("%llu%llu%llu%d", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}
	ull rand() {
		ull now = SC; now += !(now & 1);
	    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
	    ull t = SA;
		return SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;
	}
};
void print(__int128 x){
	if(x==0)return;
	print(x/10);
	putchar(x%10+'0');
}
ull k;
int T;
int main(){
	scanf("%d",&T); Mker::init();
	while(T--){
		k = Mker::rand(); 
		ull p=(sqrt((long double)4*k-3)+1)/2;
		__int128 ans;
		ull a=p-1,b=p,c=2*p-1;		
		if(a%3==0)a/=3;
		else if(b%3==0)b/=3;
		else c/=3;
		if(a%2==0)a/=2;
		else if(b%2==0)b/=2;
		else c/=2;
		ans=(__int128)a*b%md*c%md;
		p%=md;
		ull len=(k%md*ppp%md-(((p*p%md-p%md)+md)%md+1)%md*ppp%md+md+1)%md;
		p%=md;
		(ans+=len*p%md)%=md;
		print(ans);
		putchar('\n');
	}
}