#BZOJ2632. Gcd guessing game
-
ID: 1095
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Gcd guessing game
No submission language available for this problem.
题目描述
给定一个数n ,有一个数x , ( 1<=x<=n ) 每次你可以猜在[1,n]中的数,假设是y，如果x==y，游戏结束，如果没猜中，则告诉你gcd(x,y)，然后继续猜，直到猜中为止。
现在问给定n的情况下，最坏情况下最少要多少次猜中
输入格式
N
输出格式
最坏情况下最少猜中次数
6
2
数据范围与约定
2 ≤ n ≤ 10000.