atcoder abc342 D

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n,a[200010],b[200010],ans;

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i ++)
	{
		cin >> a[i];
		for(int j = 2;j <= a[i] / j;j ++)
		{
			while(a[i] % (j * j) == 0) a[i] /= (j * j);
		}
	}
	for(int i = 1;i <= n;i ++)
	{
		if(a[i]) ans += b[a[i]],ans += b[0];
		else
		{
			ans += i - 1;
		}
		b[a[i]] ++;
	}
	cout << ans;
	return 0;
}

Joshua Microsoft

2024-05-04 13:24:14

以下是改进后的代码示例：

#include <iostream>
#include <cmath>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 数字列表存储在数组 a[] 中
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 用于统计数字出现次数的哈希表
    unordered_map<int, int> freq;
    
    // 修改数组 a[]
    for (int i = 0; i < n; ++i) {
        int num = a[i];
        for (int j = 2; j * j <= num; ++j) {
            while (num % (j * j) == 0) {
                num /= (j * j);
            }
        }
        a[i] = num;
    }

    // 计算结果
    long long ans = 0;
    long long zeroCount = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] != 0) {
            ans += freq[a[i]]++;
            ans += zeroCount;
        } else {
            ans += i;
            zeroCount++;
        }
    }

    cout << ans << endl;

    return 0;
}

这个版本的代码对内存使用进行了优化，并通过哈希表 freq 来统计数字的出现次数，以提高效率。同时，代码中添加了注释以提高可读性。

Joshua Microsoft

2024-05-04 13:22:53

这段 C++ 代码的功能是处理一个数字列表，并根据它们是否能被整数的平方整除来修改它们。然后，它使用数组 b[] 跟踪数组 a[] 中修改后的值的出现次数，并使用这些计数来计算结果，结果存储在 ans 中。以下是程序每个部分的解释：

输入和初始化：

读取一个整数 n，表示元素的数量。初始化数组 a[] 存储元素，数组 b[] 用于计数。修改数组 a[]：

对于每个元素 a[i]，如果 a[i] 可以被 j^2 整除，就会迭代地删除平方因子（例如 j^2，其中 j 是整数）。这将持续进行，直到 a[i] 不再能被任何小于等于 sqrt(a[i]) 的整数的平方整除。计算结果：

对于修改后的数组 a[] 中的每个元素：如果 a[i] 非零，将 ans 增加 b[a[i]]（值为 a[i] 的先前出现次数）和 b[0]（计算非修改的零的数量，如果有的话）。如果 a[i] 为零，将 ans 增加 i-1（实际上是计算了所有之前的元素，因为它们都将与零组合）。更新 b[] 中 a[i] 的出现次数。输出：

打印累积结果 ans。潜在问题或改进：

内部循环会检查每个 j 直到 sqrt(a[i])，并多次删除平方因子，这可能效率较低，可以进行优化。对零值（a[i] == 0）的处理可以更清晰或更明确。内存使用可以通过不使用那么大的数组 b[200010] 进行优化，除非确保修改后的 a[] 中的值将在该范围内。总的来说，这个程序处理一个列表，以唯一计数的方式处理数值，删除它们的平方因子，并使用这些计数来计算特定方式的组合。这是一个有趣的算法方法，特别是在处理值及其平方因子时

共 2 条回复