CF 577C Vasya and Petya's Game-白红宇

CF 577C Vasya and Petya's Game

阅读量：5129 次

发布时间：2019-06-13

本文共 972 字，大约阅读时间需要 3 分钟。

题意：一个游戏，A童鞋在1~n的范围里猜一个数，B童鞋询问一个集合，A童鞋要对集合里每个数做出回答，他猜的数能否给整除，B要通过这些答案得到A猜的数，最少需要猜哪些数？

解法：一个数可以由若干个质数的指数次幂相乘得到，所以只要询问小于n的所有质数的指数次幂就可以得到全部数的答案。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;vector 
                   
                     prime;void init(){ bool isprime[1005] = {0}; for(int i = 2; i <= 1000; i++) { if(!isprime[i]) { prime.push_back(i); for(int j = i + i; j <= 1000; j += i) isprime[j] = 1; } }}int main(){ init(); int n; while(~scanf("%d", &n)) { vector 
                    
                      ans; for(int i = 0; i < prime.size(); i++) { int tmp = prime[i]; while(tmp <= n) { ans.push_back(tmp); tmp *= prime[i]; } } cout << ans.size() << endl; for(int i = 0; i < ans.size(); i++) { if(i) printf(" "); cout << ans[i]; } puts(""); } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4802171.html

你可能感兴趣的文章