基础函数: // 最大公约数,欧几里得定理 int gcd(int a, int b) { return b?gcd(b, a % b): a; } // 拓展欧几里得定理 // 求解ax + by = gcd(a,b) int ext_gcd(int a, int b, int &x, int &y) { int tmp, ret; if(!b) { x = 1; y = 0;
//并查集 //注意类型匹配 const int maxn = 100002; int DSet[maxn]; void init(int n) { for(int i = 0 ; i <= n ; i ++) DSet[i] = i; } int findP(int id) { if(DSet[id] != id) DSet[id] = findP(DSet[id]); return DSet[id]; } //返回根节点ID int UnionEle(int a,int b) { a = findP(a); b