topcode SRM 577 DIV2 EllysCoprimesDiv2

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 class EllysCoprimesDiv2{
 8 public:
 9     int gcd(int x,int y){
10         while(x){
11             int r = x;
12             x = y%x;
13             y=r;
14         }
15         return y;
16     }
17     int getCount(vector<int> numbers){
18         sort(numbers.begin(),numbers.end());
19         int cnt = 0;
20         for(int i = 1; i < numbers.size(); i ++ ){
21             if(gcd(numbers[i-1],numbers[i]) != 1){
22                 int j;
23                 for(j = numbers[i-1]+1; j < numbers[i]; j ++ ){
24                     if(gcd(numbers[i-1],j) == 1 && gcd(j,numbers[i]) == 1){
25                         cnt += 1;
26                         break;
27                     }
28                 }
29                 if( j >= numbers[i]) cnt +=2;
30             }
31         }
32         return cnt;
33     }
34 };