bzoj#P2632. [neerc2011] Gcd guessing game

[neerc2011] Gcd guessing game

题目描述

给定一个数 nn,有一个数 xx,每次你可以猜在 [1,n][1,n] 中的数,假设是 yy,如果 x=yx = y,游戏结束,如果没猜中,则告诉你 gcd(x,y)\gcd(x,y),然后继续猜,直到猜中为止。
现在问给定 nn 的情况下,最坏情况下最少要多少次猜中。

输入格式

共一行,一个整数 nn

输出格式

最坏情况下最少猜中次数。

6
2

数据规模与约定

对于 100%100\% 的数据,2n100002 \leq n \leq 100001xn1 \leq x \leq n

来源

neerc2011