Comet OJ - Contest #9 & X Round 3B

以你之姓@ 2023-06-02 11:56 9阅读 0赞

[Comet OJ - Contest \#9 & X Round 3B][Comet OJ - Contest _9 _ X Round 3B]  
其实这个题我一开始,完全⑧会.  
题目里给了个关于素数的定理,就考虑一下素数在这题里扮演什么样的角色.  
然后你发现,如果他第\\(0\\)天告诉了一个素数,那么只需要一天所有人就都知道了.  
如果是一个合数,那么第一天所有素数会知道消息,第二天所有人就都知道了.  
需要注意的是,要考虑它第\\(0\\)天告诉一个素数时,如果这个素数的倍数也在这个区间内,是需要两天的.  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } int n , k ; inline bool check (int x) { if ( x == 1 ) return false ; for (int i = 2 ; i * i <= x ; ++ i) if( x % i == 0 ) return false ; return true ; } signed main (int argc , char * argv[] ) { n = rint () ; k = rint () ; if ( n == 2 ) puts ("1") ; else if ( check ( k + 1 ) ) { if ( ( ( k + 1 ) << 1 ) <= n + 1 ) puts ("2") ; else puts ("1") ; } else puts ("2") ; system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11416052.html

[Comet OJ - Contest _9 _ X Round 3B]: https://cometoj.com/contest/64/problem/B?problem_id=3516