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

辗转相除法：

用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。

例如：27和6.  27%6=3.  6%3=0.  所以最大公约数为3.

public int gcd(int a, int b){
        while (b != 0){
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

最大公约数和最小公倍数的关系：

两个数的乘积等于这两个数的最大公约数与最小公倍数的乘积。假设有两个数是a、b，它
们的最大公约数是B，最小公倍数是q。那么存在这样的关系式：ab=pg。

于是代码为：

class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int num = 0;
        for(int i=0;i<nums.length;i++){
            int cur = nums[i];
            for(int j=i;j<nums.length;j++){
                cur = cur*nums[j]/gcd(cur,nums[j]);
                if(cur==k){
                    num++;
                }else if(cur>k){
                    break;
                }
            }
        }
        return num;
    }

    //用辗转相除法写gcd
    public int gcd(int a, int b){
        while(b!=0){
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
}