关于程序员: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;}