2748.美丽下标对的数目

#easy

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 9999
• nums[i] % 10 != 0

解决思路

辗转相除法

由于题目中需要判断两个数互质，所以使用辗转相除法判断，降低时间复杂度。

// 辗转相除法
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); 

由于数组长度为100，因此双重循环的时间复杂度够。

int countBeautifulPairs(int* nums, int numsSize) {
    //统计个数 
    int sum = 0;
    //i严格小于nums.length
    for (int i = 0; i < numsSize - 1; i++) {
        int first_digit = nums[i];
        //通过循环获得第一位数
        while (first_digit >= 10) {
            first_digit /= 10;
        }
        //j严格大于i
        for (int j = i + 1; j < numsSize; j++) {
            if (gcd(first_digit, nums[j] % 10) == 1)
                sum++;
        }
    }
    return sum;
}