1-1 奇偶判断
if((a&1) == 0)//判断a是否为偶，需要加上括号， ！ > 算术运算符 > 关系运算符 > && > || > 赋值运算符
1-2 数组与int的转换（PAT A1069）
int int_to_array(int a,int b[]){//低位在前
int num = 0;
while(a/10){
b[num++] = a%10;
a /= 10;
}
b[num++] = a%10;
return num;
}
int array_to_int(int b[],int num){
int sum = 0;
for(int i = 0;i < num;++i){
sum = sum*10+b[num-i-1];
}
return sum;
}
1-3 最大公约数/最小公倍数
// (原理：gcd(a,b) = gcd(b,a%b) ： greatest common divisor)
// 使用条件：保证a >= b
int gcb(int a,int b){
if(a < b){
swap(a,b);
}
if(b == 0)
return a;
else
return gcb(b,a%b);
}
int gcd(int a,int b){ (使用3目运算符简化代码)
if(a < b)
swap(a,b);
return !b ? a : gcd(b,a%b);
}
求最小公倍数： the least common multiple
int d = gcd(a,b);// 求最小公倍数必须先求得最大公因数
最小公倍数 = a*b/d; 为避免溢出，通常写成：a/d*b;
1-4 分数的运算
表示：
struct Fraction{
long long up,down; //为避免溢出，一般采用long long型
};
/*三项规定：
1.分数的正负性由分子决定
2.分子为0,分母则为1
3.分子分母没有除1以外的最大公约数
*/
//将分式化成最简分式，所有需要加减乘除的分数都需要用reduction格式化
Fraction reduction(Fraction result){
if(result.down < 0){
result.up = -result.up;
result.down = -result.down;
}
if(result.up == 0){
result.down = 1;
}else{
int d = gcd(abs(result.up),abs(result.down));
result.up /= d;
result.down /= d;
}
return result;
}
// 分式的加减乘除（以除法为例）//必须保证分式的分母不为0
Fraction divide(Fraction f1,Fraction f2){
Fraction result;
result.up = f1.up * f2.down;
result.down = f1.down * f2.up;
return reduction(result); //将分式化为最简分式
}
// 分数的加法：
Fraction add_f(Fraction a,Fraction b){
Fraction sum;
sum.up = a.up * b.down + b.up * a.down; //即便采用long long，这一步很容易溢出，慎用
sum.down = a.down * b.down;
sum = reduction(sum);
return sum;
}
// 分式的输出（3种情况）：
void showResult(Fraction r){
r = reduction(r); //首先化为最简分式
if(r.down == 1) //整数
printf("%lld",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);
}
}
/*
几个坑点：
1.分数初始化为0，分子置0，分母置1 ！，从而可以令自己定义的加减乘除可用。*/
1-5 质数的判断，获取，分解
定义：对任意正整数a(1<a<n),都有 n%a != 0成立，则n是素数。
素数的判断O(n½)：
bool isPrime(int n){
if(n <= 1) return false;
int sqr = (int)sqrt(1.0*n); //注：sqrt的参数是浮点型
for(int i = 2;i <= sqr;i++){
if(n % i == 0) return false;
}
return true;
}
素数表的获取：
法一:利用素数的判断枚举（n在10^5内）
法二：Eratosthenes求质数方法（最简单易理解：O（n*loglogn））
const int maxn = 101; //maxn：筛选到素数范围，pNum为筛选出的素数个数
int prime[maxn],pNum = 0;
bool p[maxn]; //标记数组：true代表不是素数，false代表不是素数，初始化都是素数，用memset初始化
void Find_Prime(){
for(int i = 2;i < maxn;i++){ //znj
if(p[i] == false){
prime[pNum++] = i;
for(int j = i+i;j < maxn;j += i){
p[j] = true;
}
}
}
}
质因数分解流程（需要获取质数表）
思路：s1:枚举1~sqrt(n)范围内所有质因子p,判断p是否是否是n的因子：
是：让n不断除以p，直到p不再是结果的质因子
否：跳过
s2:枚举完毕，n仍然大于1，n还有一个质因子就是n本身
1-6 大整数的加减乘除
- 这里的乘除仅仅实现了大整数与1位数字的乘除
// (口诀：bign开始初始化，大+要进位，大-要去0，大*进位要剥削)
struct bign{
int d[1000]; //大整数位数可自行调整
int len;
bign(){ //构造函数初始化
memeset(d,0,sizeof(d));
len = 0;
}
};
bign change(char str[]){ //将字符数组转换为大整数存储
bign a;
a.len = strlen(str);
for(int i = 0;i < a.len;++i){
a.d[i] = str[a.len-i-1] - '0'; //逆序存储，保证低位在前，方便后面大整数的运算
}
return a;
}
int compare(bign a,bign b){
if(a.len > b.len) return 1;
else if(a.len < b.len) return -1;
else{
for(int i = a.len-1;i >= 0;i--){
if(a.d[i] > b.d[i]) return 1;
else return -1;
}
return 0;
}
return 0;
}
/**********大整数加法**********/
bign add(bign a,bign b){ //每一位由三部分组成：操作位1，操作位2，进位 a+b
bign c;
int carry = 0;//进位
for(int i = 0;i < a.len || i < b.len;++i){ //低位在前方便进位
int temp = a.d[i]+b.d[i]+carry;
c.d[c.len++] = temp%10;
carry = temp/10;
}
if(carry != 0) //不要忘记最后一位进位
c.d[c.len++] = carry;
return c;
}
/********大整数减法****************/
bign sub(bign a,bign b){ //使用时需保证a > b,调用函数前需要一定的处理
bign c;
for(int i= 0;i < a.len || i < b.len;++i){
if(a.d[i] < b.d[i]){
a.d[i + 1]--;
a.d[i] += 10;
}
c.d[c.len++] = a.d[i] - b.d[i];
}
while(c.len -1 >= 1 && c.d[c.len-1] == 0){ // 1.去掉多余的0 2.保证至少有一位数
c.len--;
}
return c;
}
/*******大整数与整数相乘********/
bign multi(bign a,int b){ //平常计算时是一位一位的算，由于正常大脑只能口算10以内的乘法，
bign c; //计算机可以迅速算出基本数据类型的加减乘除，所以可以将整数作为一个整体乘上去
int carry = 0;
for(int i = 0;i < a.len;++i){
int temp = a.d[i]*b + carry;
c.d[c.len++] = temp%10;
carry = temp/10; //高位作为新的进位
}
while(carry != 0){ //注意与加法进行区分
c.d[c.len++] = carry%10;
carry /= 10;
}
return c;
}
/******大整数与整数相除*******/
bign divide(bign a,int b,int& r){ //除法未必除进，如需要余数需另外修改
bign c;
c.len = a.len;
for(int i = a.len - 1;i >= 0;i--){ //除法是由高到低，其余数要保存下来
r = r * 10 + a.d[i]; //和上一位余数结合
if(r < b) c.d[i] = 0; //不够除，该为为0
else{ //够除
c.d[i] = r/b; //商
r = r%b; //获得新余数
}
}
while(c.len-1 >= 1 && c.d[c.len-1] == 0){ //去掉多余的0，保证还剩一个0
--c.len;
}
return c;
}
2019年2月28日的笔记
参考资料
书籍《算法笔记》