欧几里德算法(GCD),又称辗转相除法。
//代码一: int gcd(int a, int b){ return b ? gcd(b, a%b):a; }
//代码二: int gcd(int a, int b){ while((a %= b) && (b %= a)) ; return a + b; }
练习题:1、Uva 10193 All
you need is love //P.S.The Beatles的歌名《All You
Need Is Love》。
//扯了一大堆,原来就是求两个数是否互质。。
#include <iostream> #include <cstring> using namespace std; int gcd(int a,int b){ return b? gcd(b, a%b):a; } int main() { int a, b; int T; char s[32]; int i, n; cin>>T;n=1; while(n<=T){ cout<<"Pair #"<<n++<<": "; cin>>s; a = 0; for(i=0;s[i];++i){ a =a*2+s[i]-'0'; } cin>>s; b = 0; for(i=0;s[i];++i){ b =b*2+s[i]-'0'; } if(gcd(a,b)==1) cout<<"Love is not all you need!\n"; else cout<<"All you need is love!\n"; } return 0; }