Leetcode6234-最小公倍数为 K 的子数组数目

结论：最小公倍数lcm(x,y)=x*y/gcd(x,y)

暴力枚举即可。

class Solution {
public:
    int get(int x,int y){
        return x*y/__gcd(x,y);
    }
    int subarrayLCM(vector<int>& a, int k) {
        int ans=0;
        int n=a.size();
        for(int i=0;i
            int g=a[i];
            for(int j=i;j
                g=get(g,a[j]);
                if(g==k) ans++;
                if(g>k) break;
            }
        }
        return ans;
    }
};

时间复杂度：O（）

空间复杂度：O（1）