关于程序员:PAT常见数学问题模板

本文对 PAT 中常见数学问题用到的模板进行了演绎：

1. 最大公约数与最小公倍数

int gcd(int a, int b){// 求取最大公约数
    return !b ? a : gcd(b, a%b);
}

int lcm(int a, int b){// 求取最小公倍数
    return a / gcd(a,b) * b;    // 先除后乘以防止溢出
}

2. 分数

// 留神，个别分数的分子分母用 long long 示意更保险，因为有时做运算时会导致 int 溢出
struct Fraction{// 分数
    int up, down;   // 分子与分母
};

Fraction reduction(Fraction result){// 分数化简
    if(result.down < 0){
        result.up = - result.up;
        result.down = -result.down;
    }
    if(!result.down)    result.up = 1;
    else{int d = gcd(abs(result.up), abs(result.down));  // 留神此处应用绝对值来求取最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

void showResult(Fraction r){// 分数输入
    r = reduction(r);
    if(r.down == 1) printf("%d", r.up);
    else if(abs(r.up) > r.down)
        printf("%d %d/%d", r.up/r.down, abs(r.up)%r.down, r.down);
    else
        printf("%d/%d", r.up, r.down);
}

3. 素数

bool is_prime(int n){// 判断素数
    if(n <= 1)  return false;
    int sqrn = (int)sqrt(1.0 * n);
    for(int i = 2; i <= sqrn; i++){// 记住是从 2 开始，并且前面是小于等于号
        if(n % i == 0)  return false;
    }
    return true;
}