39 条题解
-
5
PowderHan LV 10 @ 2017-05-08 12:45:18
/* 数学推理题~ 当且仅当n和m互质并且n与m奇偶性不同时才可遍历所有点~ 即(gcd(n,m)==1&&(n+m)%2==1) 其实可以打个表找规律 弱弱的窝来个数学证明吧 首先我们看到 设马向一个方向跳了x次而另一种非反方向跳法跳了y次 那么有马可到位置的集合S为{(xm+yn),(xn+my)} 如果n,m不是互质的话 设他们的最大公因数为x 那么必然横纵坐标都可以提出一个x 说明马能跳到的地方只有公约数倍数的点 这个很简单 我们再看 如果m n奇偶性相同的话 那么xm+yn和xn+my奇偶性必然也相同~ 这样的话就只能跳到横纵坐标奇偶性相同的点上了 所以必然不能遍历所有的点 窝讲的可能不太好 所以还是贴个真神犇的证明叭~ { 如果a,b不互质显然不能完成任务。 如果a,b同奇数，那么它不可能走到坐标(x,y)是一奇一偶的点。 下证明如果a,b不互质，且是一奇一偶那么能遍历完棋盘。 我们构造一种走法。 我们让马按如下方式跳三步： 先跳(a,b)，再跳(-b,a)，再跳(-b,-a)。 此时到达了(a-2b,b)，我们可以把原马(a,b)变成新马(a-2b,b)。 此时|a-2b|<b 因为如果a-2b是正的，且b<a-2b<2b，那么我们再减2b，它就是-b<a-2b-2b<0了。 这时，|a-2b|<b 故此时(a,b)的规模缩小，一直缩小下去，由于数是有限的，最终会缩小到1。 如果是(1,k)的话，由于每次减去的都是偶数，不会影响坐标的奇偶性，故此时还是一奇一偶，即k为偶数。 我们还是可以继续按上面这么做：(1,k)的等价马是(1,k-2) 一直可以到达边界(1,2)这是可以走遍棋盘的。 而如果是(a,b)都是奇数的话，最终的边界就是(1,1)并不能走遍棋盘。 故证完。 } 判断互质直接欧几里得算法辗转相除求出最大公约数 判断是否是1即可 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int k; int n,m; int gcd(int n,int m) { return m==0?n:gcd(m,n%m); } int main() { scanf("%d",&k); while(k--) { scanf("%d%d",&n,&m); if(gcd(n,m)==1&&(n+m)%2) cout<<'y'; else cout<<'n'; } } -
0
tootal (hzq) LV 9 @ 2016-07-16 16:14:58
据说是要mn互质且一奇一偶，但我也不知道咋回事！！！
~~~
#include <cstdio>
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
int k,m,n,i;
int main(){
for(scanf("%d",&k),i=1;i<=k;scanf("%d%d",&m,&n),
printf("%c",(gcd(m,n)==1&&(((m&1)+(n&1))&1))?'y':'n'),i++);
return 0;
}
~~~ -
0
编译成功
Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(2,9) Note: Local variable "j" not used
Linking foo.exe
16 lines compiled, 0.0 sec, 27456 bytes code, 1268 bytes data
1 note(s) issued测试数据 #0: Accepted, time = 0 ms, mem = 800 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 800 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 800 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 800 KiB, score = 20
Accepted, time = 0 ms, mem = 804 KiB, score = 100
-
0
zhangyq987 LV 8 @ 2009-09-06 13:26:59
水题！
var
k,m,n,i,j,p:longint;
function gcd(m,n:longint):longint;
begin
if m=0 then exit(n)
else gcd:=gcd((n mod m),m);
end;
begin
readln(k);
for i:=1 to k do
begin
readln(m,n);
if m>n then begin p:=m;m:=n;n:=p;end;
if ((m+n) mod 2=1)and(gcd(m,n)=1) then write('y')
else write('n');
end;
end. -
0
zhengfangyi LV 10 @ 2009-07-01 16:11:47
curimit大牛神解！！！！
佩服佩服...... -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include "stdio.h"
int gcd(int x,int y)
{
int t;
while(y!=0)
{
x=x%y;
t=x;
x=y;
y=t;
}
return x;
}
int main()
{
int n,x,y,i,t,ans[9];
scanf("%d",&n);
for(i=1;i -
0
感谢jsydtc的题解，不过辗转相减貌似最后一个点过不了（10000000 99999999 这个数据就暴露了不足）
下面把辗转相减和相除的程序都贴一下
辗转相减法：
Function gcd(x,y:longint):longint;
var
a,b:longint;procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a;
a:=b;
b:=temp;
end;begin
a:=x;
b:=y;
while ab do
begin
a:=abs(a-b);
swap(a,b);
end;
exit(a);
end;辗转相除法：
Function gcd(x,y:longint):longint;
var
a,b:longint;procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a;
a:=b;
b:=temp;
end;begin
a:=x;
b:=y;
while b0 do
begin
a:=a mod b;
swap(a,b);
end;
exit(a);
end;最终秒杀：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：运行超时...
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：60 有效耗时：0ms
var
c,m,i,n:integer;
begin
readln(c);
for i:=1 to c do
begin
readln(m,n);
if not(odd(m+n))then write('n')
else begin
while(m0)and(n0)do
if m>n then m:=m mod n
else n:=n mod m;
if (m=1)and(n=0)then write('y')
else if (n=1)and(m=0)then write('y')
else write('n');
end;
end;
end.???Why?
PowderHan
LV 10
@ 2017-05-08 12:45:18
