본능적으로 첫 번째 배열의 숫자들의 공배수이면서 두 번째 배열의 숫자들의 공약수인 수가 몇개인지 세어보고 싶을 것이다.
그러나 각 배열의 숫자가 10개 뿐이지만, 충분히 int값 상한을 넘길 수 있다. 예외 처리를 하기엔 골아프므로 long long을 쓴다.
|
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 54 55 56 57 |
long long getGcd(vector<long long>& a) { long long r = a.front(), v; for(int i = 1; i < a.size(); i++) { v = a.at(i); while( r != v && r * v > 0 ) { r > v ? r ^= v, v ^= r, r ^= v : v -= v/r*r; } } return r; } long long getGcd(long long a, long long b) { vector<long long> v = {a, b}; return getGcd(v); } long long getGcd(vector<int>& a) { vector<long long> b; for(auto i : a) { b.emplace_back(i); } return getGcd(b); } int getLcm(vector<int>& a) { long long ret = a.front(); for(int i = 1; i < a.size(); i++) { ret *= a.at(i) / getGcd(a.at(i), ret); } return ret; } int getTotalX(vector<int> a, vector<int> b) { int ret = 0; long long lcm = getLcm(a), gcd = getGcd(b); for(int i = lcm; i <= gcd; i += lcm) { gcd == gcd/i*i ? ret++ : 0; } return ret; } |
배열의 크기가 작으므로 숫자 하나 하나 나머지 연산을 하는 것이 더 편할 수 있다.
|
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 |
int getTotalX(vector<int> a, vector<int> b) { int ret = 0; sort(a.begin(), a.end()), sort(b.begin(), b.end()); vector<int> c; unordered_set<int> d; for(int i = a.back(); i <= b.front(); i++) { d.insert(i); } for(int i = 0; i < a.size(); i++) { c.clear(); c.reserve(d.size()); for(auto j : d) { if(0 != j % a.at(i)) c.push_back(j); } for(auto j : c) { d.erase(j); } } for(int i = 0; i < b.size(); i++) { c.clear(); c.reserve(d.size()); for(auto j : d) { if(0 != b.at(i) % j) c.push_back(j); } for(auto j : c) { d.erase(j); } } return d.size(); } |