打卡信奥刷题（3248）用C++实现信奥题 P8574 「DTOI-2」星之影

rogeliu

443人浏览 · 2026-05-12 08:28:50

rogeliu · 2026-05-12 08:28:50 发布

P8574 「DTOI-2」星之影

题目背景

闻是白极影，见时方立竿。

题目描述

白极影化为立竿之人莅临人间，带来了星之函数 $f (x)$ ，它的值为最接近于 $x4\sqrt[4]x$ 的整数$\$（即 $f(x)=⌊x4+12⌋f(x)=\left\lfloor\sqrt[4]x+\dfrac12\right\rfloor$ ； $⌊u⌋\lfloor u\rfloor$ 为对 $u$ 向下取整后的值）。

现有 $t$ 个数字 $n$ ，对于每个 $n$ ，立竿人想知道 $∑i=1n1f(i)\sum\limits_{i=1}^n\dfrac1{f(i)}$ 的值是多少，请你告诉它吧。

~~因为立竿人很急，所以~~本题的 $t$ 组询问强制在线，后一个询问需通过前一个询问的答案生成。

可用以下 C++ 代码生成（其他语言同理；需包含 <stdio.h>）：

typedef long long ll;
char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){
	//last_ans<n<=1e18
	sprintf(buf_ans,"%.6f",last_ans);
	for(ll i=0,x=0;;i++){
		if(buf_ans[i]=='.')return get_n^x;
		if(i&1)x*=10;
		else x=x*10+(buf_ans[i]^48);
	}
}

该函数第一个参数为上一次询问的答案（第一次询问时该值为 $0$ ，也就是说第一个数未经加密），第二个参数为这一次读入的被加密的数，函数返回解密后的 $n$ 。

输入格式

第一行一个整数 $t$ ，表示数据组数（询问次数）。

对于每组数据，仅一行一个整数表示加密后的 $n$ （第一个 $n$ 未被加密）。

输出格式

每行输出一个六位小数，表示答案。

输入输出样例 #1

输入 #1

7
1
5
12
95
2040
1145141920209
1070909051

输出 #1

1.000000
4.000000
6.500000
38.666667
403.857143
1475989956.412959
1.000000

说明/提示

样例解释

样例#1 解密后各组询问分别是：
$\def\r{\cr\hline} \def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{t}&1&2&3&4&5&6&7\r \textbf{n}&1&4&8&89&2022&1145141919810&1\r \end{array}$

数据范围

本题采用捆绑测试。
$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & t= & n\le&\bm{\textbf{Score}} \cr\hline 1 & 10&10^6 & 2 \cr\hline 2&1000&10^6&13\cr\hline 3&100&10^9&15\cr\hline 4 &1000&10^{18}&40\cr\hline 5 &%\text{No Special Constraints} 5\times10^5&10^{18}& 30 \cr\hline \end{array}$

对于 $100%100\%$ 的数据， $\le t \le 5\times10^5$ ， $\le n \le 10^{18}$ 。

计分规则

本题采用 $Judge\textbf{Special Judge}$ ，令你输出的答案为 $pans\text{pans}$ ，标答答案为 $jans\text{jans}$ ，如果 $∣pans−jans∣<jans×10−5\vert \text{pans}-\text{jans}\vert<\text{jans}\times10^{-5}$ 那么该组数据通过，在一个测试点内只有所有 $t$ 组数据通过该测试点才算通过。

注意后一个 $Subtask\text{Subtask}$ 对前一个 $Subtask\text{Subtask}$ 有依赖关系，即如果你没有在前一个 $Subtask\text{Subtask}$ 拿到分，那么你即使通过后一个 $Subtask\text{Subtask}$ 的所有测试点，你也无法拿到后面的分数。

C++实现

#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
int n,m,t;
int get(int x){//求1/1~1/n的所有项的和 
	return (2*x*(x+1)*(x*2+1)+3*x)/3;
}
int count(int x){
	return x*x*(x+1)*(x+1)+x*(x+1)/2;
} 
int find(int n){//寻找第n个数是属于a的哪一个元素 
	return (sqrt(sqrt(1.0+16.0*n))+1)/2;
} 
double solve(int t){
	double ans=0;
	int now=find(t);
//	printf("%lld \n",now);
	ans+=get(now-1);
	ans+=1.0*(t-count(now-1))/now;
	return ans;
}
typedef long long ll;
char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){
	//last_ans<n<=1e18
	sprintf(buf_ans,"%.6f",last_ans);
	for(ll i=0,x=0;;i++){
		if(buf_ans[i]=='.')return get_n^x;
		if(i&1)x*=10;
		else x=x*10+(buf_ans[i]^48);
	}
}
signed main(){
	scanf("%lld",&t);
	double lst=0;
	while(t--){
		int x;
		scanf("%lld",&x);
		x=next_n(lst,x);
		printf("%.6f\n",lst=solve(x));
	}
}