+⊕3\% (Розбір)

Розв'язок Спочатку ігноруємо умову XOR. Максимізація $abc$ за умови a+b+c=x над невід'ємними дійсними числами дається нерівністю AM–GM: єдиний максимум досягається при a=b=c=x/3, а добуток строго зменшується при віддаленні від цієї точки. Нехай m=\lfloor x/3\rfloor і

Тоді $abc$ спадає за $\delta$, отже відповідь — це допустима трійка з найменшим $\delta$, а вся задача зводиться до того, наскільки великим може бути змушене стати $\delta$. Умова 3\mid a\xor b\xor c лише відсікає кандидати; вона не створює кращого. Вона також не залежить від величини, оскільки (a\xor b\xor c)\bmod 3 визначається молодшими бітами, які змінюються непередбачувано, коли елементи зсуваються на одиницю. Тому серед кількох послідовних зсувів навколо $m$ деяка трійка виживає, а серед тих, що лишилися найближчими до балансу, і є оптимальна. Оцінка така:

тому для кожного x\ge 2 оптимальна трійка має всі три елементи в [m-2,\,m+2]. Рівність досягається рівно на сімействі (m,m,m+4), яке виникає при x=10,19,55,199, даючи (2,2,6), (5,5,9), (17,17,21), (65,65,69); там збалансовані кандидати (m,m,m+1) і (m,m+1,m+1) та їхні найближчі сусіди одночасно не проходять перевірку на подільність. Отже, перебір a,b\in[\max(0,m-2),\,m+2] з c=x-a-b перевіряє не більше $25$ кандидатів і серед них містить оптимальний. Для x=1 єдина трійка — (1,0,0), для якої 1\xor 0\xor 0=1; це єдине $x$, для якого не існує допустимої трійки, а x\ge 2 усуває цю проблему. Для x=2 кожна трійка містить нуль, тому відповідь дорівнює $0$. При x=10^6 відповідь приблизно 3.7\cdot 10^{16}, що переповнює 32-бітні акумулятори в мовах із фіксованими типами. Вікно фіксоване, тож час роботи становить $O(1)$ на тест і $O(t)$ загалом.

def solve():
    x=int(input())
    m=x//3
    best=-1
    for a in range(max(0,m-2),m+3):
        for b in range(max(0,m-2),m+3):
            c=x-a-b
            if c<0 or (a^b^c)%3: continue
            if a*b*c>best: best=a*b*c
    print(best)
for _ in range(int(input())):
    solve()