+

南开大学2008年暑期ACM集训

//基本算法模块 Part1

//求两个数的最大公约数
int GCD(int a, int b){
    int t;
    if ( a < b ){
        t = a; a = b; b = t; // 交换两个数的值
    }
    while ( b != 0 ){
        t = b; b = a % b; a = t;
    }
    return a;
}

//求两个数的最小公倍数
int LCM(int a, int b){
    return a / GCD(a, b) * b;
}

//求素数表（筛选法）
void Get_Prime(int P[], int &nP){    // P为素数表数组，nP为素数的个数
    bool Prime[Max];
    memset(Prime, 1, sizeof(Prime)); // 将Prime中所有的值改为true
    int i;
    Prime[0] = Prime[1] = false;
    nP = 0;
    for ( i = 2; i < Max; ++ i ){
        if ( Prime[i] ){
            for ( j = 2 * i; j < Max; j += i ){
                Prime[j] = false;
            }
            P[nP ++] = i;
        }
    }
}

//Euler回路
//定义：经过图的每一条边一次且只有一次的回路。充要条件：图连通且没有奇点。

//Hamilton回路
//定义：经过图的每一个点一次且只有一次的回路。

//一笔画
//充要条件：图连通且奇点个数为0个或2个。