K-ekvivalentlik#531
Müsbət tam ədədlərdən ibarət çoxluğunu nəzərdən keçirək.
və sıfırdan fərqli onluq rəqəmləri olsun. Belə bir şərti ödəyərsə, və rəqəmlərinin -ekvivalent olduğunu deyirik:
Hər bir n \in K üçün, əgər -in onluq yazılışındakı istənilən bir rəqəmi dəqiq bir dəfə ilə (və ya bir ilə) əvəz olunsa, alınan ədəd də -yə aid olar.
Məsələn, üçə bölünən bütün ədədlər çoxluğudur. Bu halda , və rəqəmləri -ekvivalentdir. Həqiqətən, istənilən ədədin onluq yazılışındakı -i ilə əvəz etdikdə, bölünmə xüsusiyyəti dəyişməz.
Aydın olur ki, -ekvivalentlik ekvivalentlik münasibətidir (refleksiv, simmetrik, tranzitivdir).
çoxluğu sizə sonlu sayda disyunkt sonlu müsbət ədədlər intervalının birləşməsi kimi verilir.
Tapşırığınız -dən -dək rəqəmlər arasında ekvivalentlik siniflərini müəyyən etməkdir.
Birinci sətirdə -dəki intervalların sayı verilib (1 \le n \le 10\,000). Sonrakı sətrin hər birində a_i və b_i müsbət tam ədədləri verilib və [a_i, b_i] intervalını (yəni bütün a_i-dan b_i-yə kimi olan pozitiv tam ədədləri) təyin edir. Burada 1 \le a_i \le b_i \le 10^{18}. Həmçinin, 2 \le i \le n üçün a_i \ge b_{i-1} + 2.
Hər bir ekvivalentlik sinfini, onun elementlərini artan qaydada birləşdirərək təqdim edin.
-dən -dək rəqəmlərin bütün ekvivalentlik siniflərini leksikoqrafik artan ardıcıllıqla bir sətirdə olmaqla çap edin, hər biri ayrıca sətrdə.
Nümunə 1