НОD qarşı XOR
Optimizasiya həmişə maraqlıdır! Xüsusilə də, tamamilə zəruri olmadıqda.
Hər kəs bilir ki, bit əməliyyatları (məsələn, bit üzrə istisna və ya) rekursiv funksiyalardan (məsələn, ən böyük ortaq bölən, ƏOB) daha sürətli işləyir. Təcrübə rəhbərlərini heyrətləndirmək üçün siz şirkətin əsas layihəsindəki bütün gcd(x, y) nümunələrini daha sürətli xor(x, y) ilə əvəz etdiniz.
Bu, dünən, cümə günü baş verdi. İndi düşünürsünüz ki, yeni kodu iş mühitində yerləşdirməzdən əvvəl test etməli idinizmi... Yaxşı, gec olsa da, heç olmamasından yaxşıdır. Verilmiş a[1], ..., a[n] ardıcıllığında neçə cütlük (i, j) (1 ≤ i < j ≤ n) gcd(a[i], a[j]) = xor(a[i], a[j]) bərabərliyini təmin edir. Xatırladaq ki, gcd(x, y) x və y-nin ən böyük ortaq böləni, xor(x, y) isə x və y-nin bit üzrə istisna və ya əməliyyatıdır.
Giriş məlumatları
Birinci sətir testlərin sayı z (1 ≤ z ≤ 20) ilə başlayır. Sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri tam ədəd n (1 ≤ n ≤ 2 000 000) ehtiva edir. İkinci sətir müsbət və 10^6-dan böyük olmayan tam ədədlər a[1], a[2], ..., a[n] ehtiva edir.
Bütün testlər üzrə ardıcıllıqların ümumi uzunluğu 3 * 10^7-dən çox deyil.
Çıxış məlumatları
Hər bir giriş məlumat dəsti üçün bir tam ədəd çıxarın: i < j olan və gcd(a[i], a[j]) = xor(a[i], a[j]) bərabərliyini təmin edən (a[i], a[j]) cütlərinin sayı.