首页 > 试题广场 >

猜数游戏

[编程题]猜数游戏

热度指数：2049 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛和羊羊在玩一个有趣的猜数游戏。在这个游戏中,牛牛玩家选择一个正整数,羊羊根据已给的提示猜这个数字。第i个提示是"Y"或者"N",表示牛牛选择的数是否是i的倍数。
例如,如果提示是"YYNYY",它表示这个数使1,2,4,5的倍数,但不是3的倍数。
注意到一些提示会出现错误。例如: 提示"NYYY"是错误的,因为所有的整数都是1的倍数,所以起始元素肯定不会是"N"。此外,例如"YNNY"的提示也是错误的,因为结果不可能是4的倍数但不是2的倍数。
现在给出一个整数n,表示已给的提示的长度。请计算出长度为n的合法的提示的个数。
例如 n = 5:
合法的提示有:
YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY
YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY
所以输出12

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10^6),表示已给提示的长度。

输出描述:

输出一个整数,表示合法的提示个数。因为答案可能会很大,所以输出对于1000000007的模

示例1

输入

输出

算法知识视频讲解

Python

智．之水叶神

看来最后一道题真的不简单，提交三次才做出正确答案。第一次思路不对就如@EDG_Clearlove7同学说的那样，素数幂次的情况考虑不周，第二次思路正确但是查找素数的算法过于繁琐超时了。把超时和正确的代码都贴上供大家参考吧。

1.超时方案：

importsysdef primenum(n):    from math importsqrt    ifn%2== 0:         returnn==2     ifn%3== 0:         returnn==3     ifn%5== 0:         returnn==5     forp in xrange(7,int(sqrt(n)+1),2):        ifn%p == 0:             return0     return1 
 def maxn(x,y):    res=x;n=0    whileres<=y:        n += 1        res*=x     returnn 
 if__name__ == "__main__":    n = int(sys.stdin.readline().strip())    #n+=2    max_n = 1    fori in xrange(2,n+1):        ifprimenum(i):            l=maxn(i,n)            max_n *= (l+1) 
     print max_n % 1000000007

********************************************************

2.正确方案：

   importsys  
   def prime(n):  
       flag = [1]*(n+2)  
       p=2  
       res=[]  
       while(p<=n):  
      
           res.append(p)  
           fori in range(2*p,n+1,p):  
               flag[i] = 0  
           while1:  
               p += 1  
               if(flag[p]==1):  
                   break  
       returnres[:]  
      
   def maxn(x,y):  
       res=x;n=0  
       whileres<=y:  
           n += 1  
           res*=x  
       returnn  
      
   if__name__ == "__main__":  
       n = int(sys.stdin.readline().strip())  
       #n+=2  
       max_n = 1  
       a=[];a.extend(prime(n))  
       fori in a:  
           l=maxn(i,n)  
           max_n *= (l+1)  
      
      
       print max_n % 1000000007  