Algorithm to find GCD using Stein’s algorithm gcd(a,b) If both and b are 0, gcd is zero gcd(0, 0) = 0. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2
Category: GCD-LCM
11827
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <vector> using namespace std; vector<int> vb; int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); } int main() { int n,a; int x,y; string str; cin>>n; getchar(); stringstream iss; int mx; while(n--) { //cin>>x>>y; //cout<<gcd(x,y)<<"\n"; getline(cin,str); iss<<str; mx=0; vb.clear(); while(iss>>a) { //cout<<"sdd\n"; vb.push_back(a); } iss.clear(); for(int i=0;i<vb.size()-1;i++) { for(int j=i+1;j<vb.size();j++) { a = gcd(vb[i],vb[j]); if(a>mx) mx = a; } } printf("%d\n",mx); } return 0; } |