AT_abc480_e.Product-Bounded Arithmetic Sequences
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A sequence of positive integers A=(A1,…,A∣A∣) is called a good sequence if it satisfies all of the following conditions.
- ∣A∣≥3
- A is an arithmetic progression; that is, Ai+1−Ai=A2−A1 for all 1≤i≤∣A∣−1.
- A2−A1>0
Find the number of good sequences such that the product of all elements is at most N.
It can be proved that the answer is at most 1018 under the constraints.
一个正整数序列 A=(A1,…,A∣A∣) 被称为好序列,当且仅当它满足以下所有条件:
- ∣A∣≥3
- A 是一个等差数列;即对所有 1≤i≤∣A∣−1,都有 Ai+1−Ai=A2−A1。
- A2−A1>0
求满足所有元素乘积不超过 N 的好序列的个数。
在本题约束下,可以证明答案至多为 1018。
输入格式
The input is given from Standard Input in the following format:
N
输入从标准输入中按以下格式给出:
N
输出格式
Print the answer.
输出答案。
输入输出样例
输入#1
120
输出#1
18
输入#2
1000000000000000000
输出#2
1051148114007
说明/提示
Sample 1 Explanation:
There are 4 good sequences whose product is at most 24: (1,2,3),(1,2,3,4),(1,3,5),(2,3,4).
Constraints
- 1≤N≤1018
- N is an integer.
样例 1 解释:
满足乘积不超过 24 的“好序列”共有 4 个:(1,2,3)、(1,2,3,4)、(1,3,5)、(2,3,4)。
限制条件
- 1≤N≤1018
- N 是一个整数。
输入解题思路,AI测评打分。不知道怎么写?