nikunjsoni

1819

Apr 4th, 2021
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3. const int LIMIT = int(2e5)+1;
  4. public:
  5.     int countDifferentSubsequenceGCDs(vector<int>& nums) {
  6.         int count=0;
  7.         vector<bool> m(LIMIT, false);
  8.         for(int x: nums)
  9.             m[x] = true;
  10.        
  11.         for(int i=1; i<=LIMIT; i++){
  12.             int g = 0;
  13.             for(int j=i; j<=LIMIT && g != i; j+=i)
  14.                 if(m[j]) g = __gcd(g, j);    
  15.             if(g == i) count++;
  16.         }
  17.         return count;
  18.     }
  19. };
RAW Paste Data