[算法|数论]GCD的性质
1.等价律
gcd(x,n)=i等价于gcd(x/i,n/i)=1
2.结合律&交换律:
gcd(a1,a2)=gcd(a2,a1)
gcd(a1,a2,...,an)=gcd(a1,gcd(a2,..,an))
3.单调性/收敛性
例如:以4开头往后区间的gcd可能为: 4 4 2 2 2 2 1 1 1 1 1 1
而不可能为: 2 2 4 1 1 1 4 2 2 1 1 1
同具有收敛性的还有&&和||运算等
GCD模板:(a,b大小无影响)
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}