定理:gcd(a,b) = gcd(b,a mod b) // a和b的最大公因数,a和b的大小没影响。
①0和任意自然数的最大公约数就是那个自然数。
②互质指最大公约数等于1的两个自然数。
③1和任意数互质。
判断是否互质代码如下:(如果求最大公因数,输出b即可)
bool isrp(int a, int b){if(a==1||b==1) // 两个正整数中,只有其中一个数值为1,两个正整数为互质数return true;while(1){ // 求出两个正整数的最大公约数int t = a%b;if(t == 0) break;else{a = b;b = t;}}if(b>1)return false;// 如果最大公约数大于1,表示两个正整数不互质else return true;// 如果最大公约数等于1,表示两个正整数互质}