OPJ-1067 取石子遊戲 解題報告（數論） 取石子遊戲，betty定理

連接配接--A - 取石子遊戲 Time Limit:1000MS    Memory Limit:10000KB    64bit IO Format:%I64d & %I64u  

Description

有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。遊戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的政策，問最後你是勝者還是敗者。

Input

輸入包含若幹行，表示若幹種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。

Output

輸出對應也有若幹行，每行包含一個數字1或0，如果最後你是勝者，則為1，反之，則為0。

Sample Input

2 1
8 4
4 7      

Sample Output

0
1
0      

Hint

    題目大意：中文的= =！自己看了。。。      

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	double alpha = (1.0 + sqrt(5.0)) / 2.0;
	double beta  = (3.0 + sqrt(5.0)) / 2.0;
	int big,small;
	while(cin>>big>>small)
	{
		if(big<small)
			swap(big,small);
		int n= ceil(big/beta);
		int temp1=alpha*n;
		int temp2=beta*n;
		if(small==temp1&&big==temp2)
			cout<<0<<endl;
		else
			cout<<1<<endl;
	}
}
           

出處連接配接   大意講解：//下面的内容來自chengmingvictor

先找規律，算幾個很小的必敗狀态

1，2

3，5

4，7

6，10

8，13

…

發現所有的數恰在序列中出現一次

而且差為1，2，3，4，5，…

是以這兩個序列構成正整數集的一個分劃，猜想可以由betty定理生成（僅僅是猜想，不需要

太多的理由^_^）

其實，這兩個序列恰好對應betty定理中alpha=(1+sqrt(5))/2,beta=(3+sqrt(5))/2的情況，

是以問題解決。

這題不算出公式的話是沒法做的，因為規模太大，必敗狀态太多，沒有任何的辦法

betty定理是說，如果無理數alpha和beta滿足

1.alpha,beta>0

2.1/alpha+1/beta=1

那麼，序列{[alpha*n]}和{[beta*n]}構成自然數集的一個分劃，其中[]是取整函數

這道題對應的alpha和beta分别是(1+sqrt(5))/2,(3+sqrt(5))/2

是以alpha=1/黃金分割

beta/alpha=黃金分割

可以說跟黃金分割有關，但也隻是一種巧合吧，黃金分割還是經常出現的

//————下面是對Betty定理的解釋(Traditional BIG5)

貝蒂定理

設a、b是正無理數且 1/a +1/b =1。記P={ [na] | n為任意的正整數}，Q={ [nb] | n 為任意的正整數}，則P與Q是Z+的一個劃分，即P∩Q為空集且P∪Q為正整數集合Z+。

證明：因為a、b為正且1/a +1/b=1，則a、b>1，是以對於不同的整數n，[na]各不相同，類似對b有相同的結果。是以任一個整數至多在集合P或Q中出現一次。現證明P∩Q為空集；(反證法)假設k為P∩Q的一個整數，則存在正整數m、n使得[ma]=[nb]=k。即k < ma、nb<K+1，等價地改寫不等式為

m/(k+1)< 1/a < m/k及n/(k+1)< 1/a < n/k。相加起來得 (m+n)/(k+1) < 1 < (m+n)/k，即 k < m+n < k+1。這與m、n為整數有沖突，是以P∩Q為空集。現證明Z+=P∪Q；已知P∪Q是Z+的子集，剩下來隻要證明Z+是P∪Q的子集。(反證法)假設Z+\(P∪Q)有一個元素k，則存在正整數m、n使得[ma]< k <[(m+1)a]、[nb]< k <[(n+1)b]。 由此得ma < k ≦[ (m+1)a]-1<(m+1)a -1，類似地有nb < k ≦[ (n+1)b]-1<(n+1)b -1。等價地改寫為 m/k < 1/a < (m+1)/(k+1)及n/k < 1/b < (n+1)/(k+1)。兩式加起來，得

(m+n)/k < 1 < (m+n+2)/(k+1)，即m+n < k < k+1 < m+n+2。這與m, n, k皆為正整數沖突。是以Z+=P∪Q。

另解：當對數為（a,a*(1+sqrt(5.0))/2.0)時，必敗。。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    double small,big;
    while(cin>>small>>big)
    {
        if(small>big)
            swap(small,big);
        if(big==ceil(small*(1+sqrt(5.0))/2.0))
            cout<<0<<endl;
        else
            cout<<1<<endl;
    }
    return 0;
}