(周赛t4)6019. 替换数组中的非互质数

6019. 替换数组中的非互质数

真牛逼啊。。用栈模拟

class Solution {
public:
typedef long long ll;
int gcd (int a,int b){
    return b?gcd(b,a%b):a;
}
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int>res;
        res.push_back(nums[0]);
        for(int i=1;i<nums.size();i++){
            int cur = nums[i];
            while(res.size() && gcd(res.back(), cur)>1){
                int tmp = res.back();
                res.pop_back();
                ll lcm = 1ll*tmp * cur / gcd(tmp, cur);
                res.push_back(lcm);
                cur = res.back();
                res.pop_back();
            }
            res.push_back(cur);
        }
        return res;
    }
};