It's 2021 now, so... have you found out the problem? :)

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

Why this solution is wrong?


#include <iostream>
using namespace std;

int main()
{
int herry;
int larry;
int all;
cin >> herry;
cin >> larry;
all=herry+larry-1;
herry=all-larry;
larry=all-herry;
cout << herry << " " << larry;
return 0;
}

Edited by author 03.07.2013 01:45

LL product_mod(LL a, LL b, LL mod)
{
    a %= mod;
    b %= mod;

    LL result = 0, y = a;

    while(b)
    {
        if(b&1)
            result = ((result%mod) + y) %mod;

        y = (y + y)%mod;

        b = b >> 1;
    }

    return result%mod;
}

This is also known as the Russian peasant method for multiplication.

For example, 7x13

13 = (8 + 4 + 1)

The product is re-written as 8.7 + 4.7. 1.7

In my code, y keeps track of 7, 2.7. 4.7, 8.7, etc.
It gets added to result whenever a bit is set in b.