hdu 5512 Pagodas 扩展欧几里得推导+GCD

题目链接

题意:开始有a,b两点,之后可以按照a-b,a+b的方法生成[1,n]中没有的点,Yuwgna 为先手, Iaka后手。最后不能再生成点的一方输;

(1 <= n <= 20000) T组数据T <= 500;

思路:由扩展欧几里得知道对于任意正整数,一定存在整数x,y使得 x*a + y*b = gcd(a,b);并且这个gcd是a,b组成的最小正整数;同时也知道了这也是两个点之间的最小距离;

之后直接求点的个数即可;

ps:这道题我竟然想到了组合游戏。。明显没有说双方都要用最优策略,并且一看就应该知道之和可填的点数有关。。。思维的渣渣

#include<bits/stdc++.h>
using namespace std; int main()
{
int T,n,l,r;
scanf("%d",&T);
for(int kase = ;kase <= T;kase++){
scanf("%d%d%d",&n,&l,&r);
int gcd = __gcd(l,r);
int cnt = n/gcd;
printf("Case #%d: %s\n",kase,cnt&?"Yuwgna":"Iaka");
}
return ;
}
上一篇:简单介绍Javascript匿名函数和面向对象编程


下一篇:HDU A/B 扩展欧几里得