首页 > 代码库 > [XSY 1543] Crash的数列 找规律
[XSY 1543] Crash的数列 找规律
题意
一个序列形如 {1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, ...} , $a_i = \sum_{j}[a_j = i]$ .
给定 $n$ , 求 $a_n$ .
$n \le {10} ^ {18}$ .
分析
打表找规律.
一阶: 第 $i$ 项为 $a_i$ .
二阶: $i$ 有 $a_i$ 项.
三阶: 出现次数为 $i$ 的有 $a_i$ 项.
发现利用三阶的性质可以在 $O(\sqrt[3]{n})$ 直接求解.
实现
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #define F(i, a, b) for (register int i = (a); i <= (b); i++) 6 #define LL long long 7 8 const int N = 12000000; 9 10 LL a[N+5]; 11 12 int main(void) { 13 #ifndef ONLINE_JUDGE 14 freopen("crash.in", "r", stdin); 15 #endif 16 17 int tot = 0; 18 a[++tot] = 1, a[++tot] = 2, a[++tot] = 2; 19 for (int w = 3; w <= N && tot <= N; w++) 20 for (int i = 1; i <= a[w] && tot <= N; i++) 21 a[++tot] = w; 22 23 LL n; scanf("%lld", &n); 24 LL res = 0, cnt = 0; 25 for (int t = 1; t <= N; t++) { 26 LL _res = res + t * a[t]; 27 if (res < n && n <= _res) { 28 printf("%lld\n", cnt + (n - res - 1) / t + 1); 29 return 0; 30 } 31 res = _res, cnt += a[t]; 32 } 33 34 return 0; 35 }
[XSY 1543] Crash的数列 找规律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。