No.2318 Phys Bone Maker
タグ : / 解いたユーザー数 100
作問者 : 👑
amentorimaru
/ テスター :
tatyam
cleantted
Problem Statement
Etowanyu, an avatar in a virtual space, is configuring his tail so that it sways more the closer a part is to the tip. How cute.
When Etowanyu inputs an arbitrary sequence of positive integers $A = (A_1, A_2, \dots , A_M)$, integers $X_0, X_1, \dots, X_M$ representing the magnitude of the sway are assigned to $M+1$ places on the tail as follows.
(Note that Etowanyu can also choose the length $M$ of the sequence.)
- $X_0 = 1$
- $X_i = \text{LCM}(X_{i-1},A_i)$ (where $\text{LCM}(a, b)$ denotes the least common multiple of $a$ and $b$.)
You are given a positive integer $N$. Etowanyu wants to make a tail that satisfies the following condition.
- $1=X_0 \ < \ X_1 \ < \ \dots < \ X_M = N$
How many sequences of positive integers $A$ satisfy this condition? Since the answer can be very large, find it modulo $998244353$.
Input
$N$
- All input values are integers.
- $2 \le N \le 10^{12}$
Output
Print the number of sequences of positive integers $A$ satisfying the condition, modulo $998244353$.
Sample
Sample 1
Input
6
Output
5
The following $5$ sequences of positive integers $A$ satisfy the condition.
$A = (6) , (2,3) , (2,6) ,(3,2),(3,6)$
For example, when $A=(3,6)$, $X$ is as follows and satisfies the condition.
- $X_0=1$
- $X_1=\text{LCM}(X_0,A_1)=3$
- $X_2=\text{LCM}(X_1,A_2)=6=N$
When $A=(6,3)$, we have $X=(1,6,6)$, which does not satisfy $X_1 < X_2$.
When $A=(3,4)$, we have $X=(1,3,12)$, which does not satisfy $X_2 = N$.
Sample 2
Input
8
Output
4
Sample 3
Input
963761198400
Output
55988508
Find the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。