leetcode-Array

Link

思路：

1. nums中的数要是能整除numsDivide中的所有数，那么，其满足的条件就是整除nunsDivide中的最小公约数
2. 所以需要求numsDivide的最小公约数，需要用到辗转相乘法

    int gcb(int a,int b){
    
        return a==0?b:gcb(b%a,a);
        //举个例子，就能简单推出
        //比如，4和18的最小公约数，拿18除4的余数（为2），然后拿余数2继续跟4进行相同的运算，gcb（2，4），然后会发现这一次的4%2为0，所以就返回2，也即返回b
    }

3.这道题真正要考的地方在于（理解了题意后转化为：

1.循环nums中的每个数，找到最小的能够整除于最小公约数的数k
2.然后再遍历循环一次，这次找到所有比k小的数

class Solution {
    
    public int minOperations(int[] nums, int[] numsDivide) {
    

    //这道题重要的点在于求最小公约数的辗转相除法
    //nums中的数要是能整除numsDivide中的所有数，那么，其满足的条件就是整除nunsDivide中的最小公约数
    //所以先用辗转相除法求numsDivide中的最小公约数
    int p=0;
    for(int numsdivide:numsDivide){
    
        p=gcb(p,numsdivide);
    }
    int res=Integer.MAX_VALUE;
    int sum=0;
    //找到最小能够整除p的数
    for(int i:nums){
    
        if(p%i==0){
    
            res=Math.min(res,i);
        }
    }
    if(res==Integer.MAX_VALUE)return -1;
    for(int i:nums){
    
            if(i<res)sum++;
    }
return sum;
    }

    int gcb(int a,int b){
    
        return a==0?b:gcb(b%a,a);
        //举个例子，就能简单推出
        //比如，4 和18的最小公约数，拿18除4的余数，然后拿余数继续跟4进行相同的运算，直到余数为0，也就是上面的a=0，就返回b 比如4%2和2 4%2为0了，就返回2，也即返回b
    }
}