題目大意
給出a，b，按照圖中要求染色，問黑色格子是否是有限個（Finite），
解題思路
這是codeforce官方題解：
根據染色要求，一個格子如果能表示成\(ax+by(a,b為整數)\)的形式，那么這個格子可以被染成白色，由數學知識可以知道ax+by % gcd(a,b) = 0?，反之任意不能被\(gcd(a,b)\)整除的數都不能表示成\(ax+by\)的形式，
接下來證明，任意一個數\(x^{'}(x^{'}>=a*b)\)能用兩個互質的數\((a,b)\)來表示，
構造集合\(S = \{x^{'}, x^{'} - a, x^{'} - 2a, \dots, x^{'} - (b - 1) a\}\)，如果集合中任何一個數被染成白色，那么按照染色隊則\(x\)也被染成白色，首先\(S\)集合中有b個元素，假設這些元素都不能被\(b\)整除，（一不能整除b的數 對\(b\)的余數只有b-1個，集合中有b個數，對b取余就會產生b種余數）根據鴿巢定理，這個集合中一定存在兩個不同的數\(x^{'} - sa, x^{'} - ta \in S (s<t)\)對b取余之后余數一樣，那么\((x^{'} - sa) - (x^{'} - ta) = a (t - s)\% b=0\)，由于a，b互質，那么\(t-s\)整除\(b\)，也就是\(t-s=kb,k>=1\)，由于\(x^{'} - sa, x^{'} - ta \in S (s<t)\)，可知\(t<b,s<b,(t-s)<b\)，所以\(t-s\)整除\(b\)不成立，假設不成立，
也就是集合S中一定存在一個能整除b的數，這個能整除b的數\(x^{'}-sa\)能表示成\(ax+by\)的形式，被染成白色，這個數加上\(sa\)得到\(x^{'}\)，也能染成白色，這樣就證明了任意一個數\(x^{'}(x^{'}>=a*b)\)能表示成\(ax+by\)的形式，
#include <bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
cin>>t;
while(t--){
cin>>a>>b;
if(__gcd(a,b)==1)cout<<"Finite\n";
else cout<<"Infinite\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21312.html
標籤：其他