\[OI中的数论知识\]
\[By\;TYQ\]
gcd
\[gcd(i,j) = max \{ y | i \equiv 0 \; (mod y) , j \equiv 0 \; (mod y) \}\]
关于求gcd：
暴力
时间复杂度O(N)级别
欧几里得算法
利用定理\(gcd(i,j) = gcd(i,j-i)\;(i<j)\)
这是显而易见的...
然后我们也可以知道\(gcd(i,j) = gcd(j,i%j)\;(i<j)\)
时间复杂度是log级的 ， 是一种极为优秀的算法
//demo_gcdint gcd(int x , int y){ if(y==0)return x ; return gcd(y , x%y) ;}