33OJ
登录 注册

E. 乘积受限的等差数列

    传统题 2000ms 1024MiB

乘积受限的等差数列

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

乘积受限的等差数列

题目描述

如果一个正整数序列 A=(A1,…,A∣A∣)A=(A_1,\dots,A_{|A|}) 满足以下所有条件,就称它是一个好序列:

  • ∣A∣≥3|A|\ge 3;
  • AA 是等差数列,即对所有 1≤i≤∣A∣−11\le i\le |A|-1 都有 Ai+1−Ai=A2−A1A_{i+1}-A_i=A_2-A_1;
  • A2−A1>0A_2-A_1>0。

求所有元素之积不超过 NN 的好序列的个数。

可以证明,在本题的约束下答案不超过 101810^{18}。

输入格式

一行一个整数 NN。

输出格式

输出一个整数,表示答案。

120
18
1000000000000000000
1051148114007

数据范围

对于所有测试数据,保证 1≤N≤10181\le N\le 10^{18}。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊限制
1∼61 \sim 6 3030 55 N≤106N \le 10^6
7∼127 \sim 12 N≤1012N \le 10^{12}
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。

ABC480 赛后模拟赛✅️

未参加
状态
已结束
规则
IOI
题目
7
开始于
2026-10-23 21:40
结束于
2026-11-6 21:40
持续时间
336 小时
主持人
参赛人数
32