xay loves count
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;int a[1000005] = {0};int cnt[1000005] = {0};for (int i = 0; i < n; ++i) {cin >> a[i];cnt[a[i]]++;}long long ans = 0;for (int i = 1; i <= 1000000; ++i) {if (cnt[i]) {for (int j = 1; i * j <= 1000000; ++j) {ans += 1LL * cnt[i] * cnt[j] * cnt[i * j];}}}cout << ans << '\n';return 0;
}代码思路
-
输入读取：读取数组长度 n 和数组 a。使用一个数组
cnt来记录每个值在数组 a 中出现的次数。使用ios::sync_with_stdio(false);和cin.tie(nullptr);优化输入输出速度。读取数组长度n和数组a。使用cnt数组记录每个值在数组a中出现的次数。 -
预处理：遍历数组 a，更新
cnt数组。初始化ans为 0，用于存储满足条件的三元组数量。遍历所有可能的i，如果cnt[i]不为 0，继续遍历所有可能的j。计算i * j，如果i * j在范围内（不超过 1000000），累加cnt[i] * cnt[j] * cnt[i * j]到ans。 -
计算满足条件的三元组：遍历所有可能的 i 和 j，计算ai×aj。检查ai×aj 是否在数组 a中存在，如果存在，累加对应的次数。
-
数组初始化：使用
{0}初始化数组a和cnt，确保所有元素初始为 0。 -
循环优化：外层循环遍历
i，内层循环遍历j，确保i * j不超过 1000000。 -
类型转换：使用
1LL进行类型转换，确保乘法操作不会溢出。
1LL的用法
用法描述
1LL 是一个常量，表示一个长整型（long long）类型的数字 1。在 C++ 中，使用 1LL 进行类型转换是为了确保在进行乘法运算时，中间结果不会溢出。
在 C++ 中，整数常量默认是
int类型。当进行乘法运算时，如果操作数都是int类型，结果也会是int类型。如果结果超出了int类型的范围，会导致溢出。为了避免这种情况，可以使用1LL将其中一个操作数强制转换为long long类型，从而确保整个表达式的计算都在long long范围内进行。
代码示例
int a = 100000;
int b = 100000;
int c = 100000;
long long result = a * b * c;在这个例子中，a * b * c 的中间结果可能会超过 int 类型的最大值（通常是 2147483647），导致溢出。即使最终结果需要存储在 long long 类型的变量中，中间结果的溢出仍然会影响最终结果的正确性。
int a = 100000;
int b = 100000;
int c = 100000;
long long result = 1LL * a * b * c;1LL 将第一个操作数 a 强制转换为 long long 类型，从而使整个表达式的计算都在 long long 范围内进行，避免了中间结果的溢出。
1LL 是一个常量，表示一个 long long 类型的数字 1。在乘法运算中使用 1LL 可以确保中间结果不会溢出，从而保证计算的正确性。
