Районная олимпиада 2019-2020 информатика

Задача F. Тройки

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Дан массив $a$ длины $n$, который состоит из целых натуральных чисел. Все числа в массиве различные. Вам нужно посчитать количество троек $i$, $j$, $k$, что $i \ne j$, $i \ne k$, $j \ne k$ и $a_i*a_j=a_k^2$.

Формат входного файла

В первой строке задано одно целое число $n$ $(3 <= n <= 10^5)$. В следующей строке задано $n$ целых натуральных чисел $a_1$, $a_2$, $\dots$, $a_n$ $(1 <= a_i <= 3 * 10^5)$.

Формат выходного файла

Выведите одно целое число — ответ на задачу.

Система оценки

Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $n <= 100$, $1 <= a_i <= 500$. Тесты с номерами 1-3.
2. $n <= 5000$, $1 <= a_i <= 10000$. Тесты с номерами 4-6.
3. $n <= 10^5$, $1 <= a_i <= 300000$. Тесты с номерами 7-10.

Пример:

Вход

6
6 3 9 4 12 27

Ответ

6

( Aibar Kuanyshbay )

Комментарий/решение

Здравствуйте, эту задачу возможно решить за такие ограничение?

Решение на 60 баллов за O(n^2)

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define F first
#define S second
#define ll long long
#define all(x) x.begin(), x.end() 
#define pii pair<int, int>
#define unm unordered_map
#define pll pair<ll, ll>
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define file freopen("a.txt", "r", stdin), freopen("A.txt", "w", stdout);
const ll SIZE = (ll)3 * 1e5 + 5;
void solve(){
    int n, c = 0;
    cin >> n;
    int a[n];
    int count[SIZE]{0};
    for(int i = 0; i < n; i++){
    	cin >> a[i];
    	count[a[i]] = 1;
    }
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < n; j++){
    		ll check = sqrt(a[i] * a[j]);
    		if(i == j) continue;
    		if(check * check != a[i] * a[j]) continue;
    		if(count[check] == 1){
    			c++;
    		}
    	}
    }
    cout << c;
} 
int main(){
   speed;
   int t = 1;
   while(t--){
      solve();
   }
}

Пусть p[i] - минимальное натуральное число такое что p[i] * i - квадрат,

а также C -> максимальное число в массиве a

Тогда нетрудно заметить что p[a[i]] = p[a[j]]

Поэтому надо перебирать только такие числа что p[x] = p[y]

Нетрудно доказать что максимальный размер множества чисел с одинаковым p[i] будет равен sqrt(C)

Тогда обычный перебор будет работать за O((n / sqrt(C)) * sqrt(C) ^ 2) =

O(n * sqrt(C))

А общая асимптотика будет: O(ClogC + n * sqrt(C))

показать/скрыть код

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
using ll = long long;

const int C = 3e5 + 50;
vector<int> divisors[C], nums[C];
int prime[C], p[C], good[C];

signed main() {
    for (int i = 2; i < C; ++i) {
        if (!prime[i]) {
            for (int j = i; j < C; j += i) {
                prime[j] = 1;
                divisors[j].push_back(i);
            }
        }
    }
    p[1] = 1;
    for (int i = 2; i < C; ++i) {
        int res = 1, q = i;
        for (int d : divisors[i]) {
            int c = 0;
            while (q % d == 0) {
                c ^= 1;
                q /= d;
            }
            if (c) res *= d;
        }
        p[i] = res;
    }
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    for (int i : a) good[i] = 1;
    for (int i = 1; i < C; ++i) {
        if (good[i]) {
            nums[p[i]].push_back(i);
        }
    }
    int ans = 0;
    for (int i = 1; i < C; ++i) {
        for (int x = 0; x < nums[i].size(); ++x) {
            for (int y = x + 1; y < nums[i].size(); ++y) {
                ans += good[(int)sqrt(nums[i][x] * 1ll * nums[i][y])];
            }
        }
    }
    cout << ans * 2;
}