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