2778-特殊元素平方和

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个
特殊元素 。

返回 nums 中所有 特殊元素 的 平方和 。

示例 1：

**输入：** nums = [1,2,3,4]
**输出：** 21
**解释：** nums 中共有 3 个特殊元素：nums[1] ，因为 4 被 1 整除；nums[2] ，因为 4 被 2 整除；以及 nums[4] ，因为 4 被 4 整除。 
因此，nums 中所有元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21 。  

示例 2：

**输入：** nums = [2,7,1,19,18,3]
**输出：** 63
**解释：** nums 中共有 4 个特殊元素：nums[1] ，因为 6 被 1 整除；nums[2] ，因为 6 被 2 整除；nums[3] ，因为 6 被 3 整除；以及 nums[6] ，因为 6 被 6 整除。 
因此，nums 中所有元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63 。 

提示：

• 1 <= nums.length == n <= 50
• 1 <= nums[i] <= 50

视频讲解

算法一：遍历

按照题目要求计算即可。

[sol-Python3]

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        return sum(x * x for i, x in enumerate(nums, 1)
                         if len(nums) % i == 0)

[sol-Java]

class Solution {
    public int sumOfSquares(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                ans += nums[i - 1] * nums[i - 1];
            }
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int sumOfSquares(vector<int> &nums) {
        int ans = 0, n = nums.size();
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                ans += nums[i - 1] * nums[i - 1];
            }
        }
        return ans;
    }
};

[sol-Go]

func sumOfSquares(nums []int) (ans int) {
	for i, x := range nums {
		if len(nums)%(i+1) == 0 {
			ans += x * x
		}
	}
	return
}

[sol-JavaScript]

var sumOfSquares = function (nums) {
    const n = nums.length;
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            ans += nums[i - 1] * nums[i - 1];
        }
    }
    return ans;
};

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。

算法二：枚举

根据题意，i 是 n 的因子，此时 \dfrac{n}{i 也是 n 的因子，那么只需要枚举 \sqrt{n 以内的 i，就可以得到大于 \sqrt{n 的另一个因子了。

[sol-Python3]

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1, isqrt(n) + 1):
            if n % i == 0:
                ans += nums[i - 1] ** 2  # 注意数组的下标还是从 0 开始的
                if i * i < n:  # 避免重复统计
                    ans += nums[n // i - 1] ** 2
        return ans

[sol-Java]

class Solution {
    public int sumOfSquares(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                ans += nums[i - 1] * nums[i - 1]; // 注意数组的下标还是从 0 开始的
                if (i * i < n) { // 避免重复统计
                    ans += nums[n / i - 1] * nums[n / i - 1];
                }
            }
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int sumOfSquares(vector<int> &nums) {
        int ans = 0, n = nums.size();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                ans += nums[i - 1] * nums[i - 1]; // 注意数组的下标还是从 0 开始的
                if (i * i < n) { // 避免重复统计
                    ans += nums[n / i - 1] * nums[n / i - 1];
                }
            }
        }
        return ans;
    }
};

[sol-Go]

func sumOfSquares(nums []int) (ans int) {
	n := len(nums)
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			ans += nums[i-1] * nums[i-1] // 注意数组的下标还是从 0 开始的
			if i*i < n { // 避免重复统计
				ans += nums[n/i-1] * nums[n/i-1]
			}
		}
	}
	return
}

[sol-JavaScript]

var sumOfSquares = function (nums) {
    const n = nums.length;
    let ans = 0;
    for (let i = 1; i * i <= n; i++) {
        if (n % i === 0) {
            ans += nums[i - 1] * nums[i - 1]; // 注意数组的下标还是从 0 开始的
            if (i * i < n) { // 避免重复统计
                ans += nums[n / i - 1] * nums[n / i - 1];
            }
        }
    }
    return ans;
};

复杂度分析

• 时间复杂度：\mathcal{O}(\sqrt{n})，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。