H 模拟水题

n个人小明编号为m 从编号为a的人开始数起始数字为b 遇到素数duang 并反相求小明应该说什么

Sample Input

3
10 2 //n m
3 4 //a b
3 3
2 6
4 1
3 8

Sample Output

duang
duang
10

 1 # include <cstdio>
 2 # include <cstring>
 3 # define LL long long
 4 using namespace std ;
 5 
 6 const int MAXN=100010;
 7 bool notprime[MAXN];//值为false表示素数，值为true表示非素数
 8 void init()
 9 {
10     memset(notprime,false,sizeof(notprime));
11     notprime[0]=notprime[1]=true;
12     for(int i=2;i<MAXN;i++)
13         if(!notprime[i])
14         {
15             if(i>MAXN/i)continue;//防止后面i*i溢出(或者i,j用long long)
16             //直接从i*i开始就可以，小于i倍的已经筛选过了,注意是j+=i
17             for(int j=i*i;j<MAXN;j+=i)
18                 notprime[j]=true;
19         }
20 }
21 
22 int main ()
23 {
24    // freopen("in.txt","r",stdin) ;
25     int T ;
26     init() ;
27     scanf("%d" , &T) ;
28     while (T--)
29     {
30         int n , m ;
31         int a , b ;
32         scanf("%d %d" , &n , &m) ;
33         scanf("%d %d" , &a , &b) ;
34         bool flag = 1 ;
35         while(1)
36         {
37             if (a == m)
38             {
39                 if (notprime[b] == 0)
40                    printf("duang
") ;
41                 else
42                    printf("%d
" , b) ;
43                 break ;
44             }
45             if (flag)
46             {
47                 a++;
48                 if (a >n)
49                     a -= n ;
50                 b++ ;
51                 if (notprime[b] == 0) //是素数
52                 {
53                     flag = !flag ;
54                 }
55 
56             }
57             else
58             {
59                 a--;
60                 if (a < 1)
61                     a+= n ;
62                 b++ ;
63                 if (notprime[b] == 0)
64                 {
65                     flag = !flag ;
66                 }
67             }
68         }
69     }
70 
71     return 0 ;
72 }

View Code