#include <bits/stdc++.h> using namespace std; #define ll long long // Funkce pro výpočet počtu prvočíselných dělitelů // Např. 12 = 2*2*3 -> vrátí 3 ll count_prime_factors(ll n) { ll cnt = 0; for (ll i = 2; i * i <= n; ++i) { while (n % i == 0) { cnt++; n /= i; } } if (n > 1) cnt++; return cnt; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector<ll> x(n); vector<ll> cnt(n); // Zde uložíme "výšku" každého leknínu for (ll i = 0; i < n; i++) { cin >> x[i]; cnt[i] = count_prime_factors(x[i]); } // Procházíme všechny dvojice i < j for (ll i = 0; i < n; i++){ for (ll j = i + 1; j < n; j++){ // 1. Zkontrolujeme, jestli tam žába vůbec může skočit (dělitelnost) if (x[j] % x[i] != 0) { // Pokud nedělí, nemůže skočit, takže barva nehraje roli. // Vypíšeme třeba barvu 1. cout << 1 << " "; } else { // 2. Pokud dělí, musíme chytře obarvit // Použijeme XOR jejich "výšek" (počtu dělitelů) ll diff = cnt[i] ^ cnt[j]; // Najdeme nejvýznamnější bit (Most Significant Bit) // __builtin_clzll vrací počet nul zleva u long long (64 bit) // 63 - clzll nám dá index nejvyšší jedničky (0-indexed) ll msb_index = 63 - __builtin_clzll(diff); // Barva je index bitu modulo 3 (+1 aby to bylo 1,2,3) cout << (msb_index % 3) + 1 << " "; } } // Nový řádek po vypsání všech dvojic pro dané i (volitelné formátování) // Zadání to asi nevyžaduje, ale pro přehlednost: // cout << "\n"; } cout << "\n"; return 0; }