首页 > > 程序设计 > C/C++ >

HDU_5512_Pagodas

2018-06-17 21:48:13来源：未知阅读 ()

Pagodas

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2045 Accepted Submission(s): 1405

Problem Description

Input

The first line contains an integer

Output

For each test case, output the winner (``Yuwgna" or ``Iaka"). Both of them will make the best possible decision each time.

Sample Input

16 2 1 2 3 1 3 67 1 2 100 1 2 8 6 8 9 6 8 10 6 8 11 6 8 12 6 8 13 6 8 14 6 8 15 6 8 16 6 8 1314 6 8 1994 1 13 1994 7 12

Sample Output

Case #1: Iaka Case #2: Yuwgna Case #3: Yuwgna Case #4: Iaka Case #5: Iaka Case #6: Iaka Case #7: Yuwgna Case #8: Yuwgna Case #9: Iaka Case #10: Iaka Case #11: Yuwgna Case #12: Yuwgna Case #13: Iaka Case #14: Yuwgna Case #15: Iaka Case #16: Iaka

Source

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

签到数论题
求gcd(a,b)=d，如果a和b互质则可以到达每个位置，否则总共到达位置数量为n/d

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int gcd(int x, int y){
25     return y?gcd(y,x%y):x;
26 }
27 int T, n, a, b, c, d, Yuwgna;
28 int main(){
29     // freopen("in.txt","r",stdin);
30     // freopen("out.txt","w",stdout);
31     while(~scanf("%d",&T)){
32         for(int kase=1;kase<=T;kase++){
33             scanf("%d %d %d",&n,&a,&b);
34             d=gcd(a,b);
35             c=(n/d)-2;
36             Yuwgna=c&1;
37             printf("Case #%d: %s\n",kase,Yuwgna?"Yuwgna":"Iaka");
38         }
39     }
40     return 0;
41 }