c++ уникальные пары делителей

Question

Ввод:

В первой строке ввода программа получает число n (размер массива), затем в следующей строке задаются n натуральных чисел, каждое из которых находится в диапазоне [1, 1000000].

Вывод:

Сколько уникальных пар (a, b) можно создать из заданного выше набора при условии что a - делитель b.

1 ≤ n ≤ 500 000

Ввод

7 32 1 2 3 2 4 16 вывод

12

делал что то в этом роде, но из этого всего правильный только размер масива я думаю, ибо считает не совсем то что нужно

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int Rozmier, n;
    cout << "Enter an array size:" << "\n";
    cout << "Rozmier mas = ";
    cin >> Rozmier;
    int* arr = new int[Rozmier];
    cout << "Enter an array:" << "\n";
    for (int i = 0; i < Rozmier; i++)
    {
        cin >> arr[i];
    }
    n = 0;
    for (int i = 0; i < Rozmier - 1; i++)
    {
        if (arr[i+1] > arr[i] && i % 2 == 0)
            n++;
    }
    cout << "The searched number of pairs: " << n << "\n";
    delete [] arr;
    return 0;
}

Answer 1

Используй массив в котором индекс будет значением:

https://ideone.com/SJCMcG

a = [32, 1, 2, 3, 2, 4, 16]

c = [0] * 1000001
for x in a: c[x] += 1
c1 = [1 if x else 0 for x in c]

same = sum(x > 1 for x in c)
diff = sum(sum(c1[i*2::i]) for i in range(1, len(c)) if c1[i])

print(same + diff)

Answer 2

Долго разбирался как сделать set в c++. Вот решение, которое тупо создает множество подходящих пар и потом выдаёт размер этого множества. В общем для больших n оно не работает. Но оставлю.

#include <iostream>
#include <set>
#include <bits/stdc++.h>


using namespace std;
struct div_pair
{
    int dividend;
    int divisor;
};

bool operator==(const div_pair& p1, const div_pair& p2) {
    return p1.dividend == p2.dividend && p1.divisor == p2.divisor;
}


namespace std
{
    template<> struct hash<div_pair>
    {
        size_t operator()(div_pair const& dp) const noexcept
        {
            size_t h1 = hash<int>{}(dp.dividend);
            size_t h2 = hash<int>{}(dp.divisor);
            return h1 ^ (h2 << 1);
        }
    };
}

int main()
{
    int size;
    unordered_set<div_pair> div_pairs;
    cout << "Enter an array size:" << "\n";
    cout << "size mas = ";
    cin >> size;
    int* arr = new int[size];
    cout << "Enter an array:" << "\n";
    for (int i = 0; i < size; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i <=size-2; i++)
    {
        for(int j=i+1;j<=size-1;j++)
        {
            div_pair working_pair;
            int dividend=max(arr[i],arr[j]);
            int divisor=min(arr[i],arr[j]);
            if(dividend%divisor==0)
            {
                working_pair.dividend=dividend;
                working_pair.divisor=divisor;
                div_pairs.insert(working_pair);
            }

        }
    }
    cout << "The searched number of pairs: " << div_pairs.size() << "\n";
    delete [] arr;
    return 0;
}

БЛОГ НА HUSL

c++ уникальные пары делителей

Ответы (2 шт):