Pagodas HDU - 5512

題意：

一開始給你兩個數a和b，你可以得到c通過，c=a+b，或者c=a-b，你所能得到的數的范圍是1~n，兩個人輪流操作，當有一方無法操作時，另一方獲勝

題解：

c=a+b,c=a-b
我們可以發現所得數都滿足ax+by，而根據裴蜀定理：對于任意的正整數a,b,一定存在非零整數x,y,使得xa+yb=gcd(a,b),對于任意的xa+yb=d,d一定是gcd(a,b)的倍數
所有1~n中可以被操作生成的數的數量為n/gcd(a,b),因為一開始給了你兩個，所以還要減2，n/gcd(a,b)-2

代碼：

#include<bits/stdc++.h> using namespace std; int gcd(int a,int b){if(b)return gcd(b,a%b);return a; } int main(){int t;scanf("%d",&t);int cas=0;//cout<<gcd(6,8);while(t--){int n,a,b;scanf("%d%d%d",&n,&a,&b);int minn=gcd(a,b);int num=n/minn-2;if(num%2==0)printf("Case #%d: Iaka\n",++cas);else printf("Case #%d: Yuwgna\n",++cas);}return 0; }

總結

以上是生活随笔為你收集整理的Pagodas HDU - 5512的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。