I already stuck with my solutions at least 5 times, it's ok, I need fresh ideas :)

One of my first ideas was with segment tree and LCM.
1) We calculate order for every element.
2) It is easy to combine 2 segments. order(combined) = LCM(order(segment1), order(segment2))
3) But it hard to do multiplication.

If we multiply by m, we cannot just do order=LCM(order(m), order(segment)). Counterexample:
p=17
segment=[2] order(segment)=8
m=2
after multiplication
segment=[4] order(segment)=4
4 != LCM(order(2), order(segment)) = 8

I am trying to find a way how to express segment of any length in a short way (lets call it segment_data), so it has next properties:
1) I can calculate order quickly
2) I can create multiplication procedure over segment_data
3) Multiplication over segment_data leads to the same order as multiplication over raw segment
4) I can combine 2 segment_data into 1 (so I can build segment tree)

If segment_data is just order of a segment, I cannot make it work (example above). Property 3 is not working.

My last idea was to use segment_data = array of 2 elements (I understand I was not very clear in first post, it is confusing even for me). I found next: there are group of segments, that behaves exactly the same for our task.
I mean, if:
     for any i in (1..p-1): order(i * segment1) = order(i * segment2)
Then we can replace segment1 with segment2, and nothing changes for our task.
I generated groups of such segments for different p.
Example:
p=17

[6,7,10,12] can be replaced with [3,6]
after multiplication by 1..p-1, they lead to the same picture of orders:
[16 16 8 16 8 8 8 16 16 8 8 8 16 8 16 16]

[6,7,10,11] can be replaced with [6,7], picture
[16 16 4 16 4 8 8 16 16 8 8 4 16 4 16 16]

When I was investigating behavior of similar segments, I noticed segment of any length can be replaced with segment of length 2. And it will have the same properties. The plan was to have 2 numbers as nodes of segment tree. But I stuck with combining procedure.

Edited by author 29.05.2021 18:42