Building a data structure

Question

Given natural number m≥2, I need to think of a data structure, for a group of natural numbers which will support the following functions, with run-time restriction:

Init() - Initialize the the data structure - O(1)
Insert(k) - Insert a new number k to the data structure (only if does not exist). - O(logn)
delete(k) - delete number k from the data structure. - O(logn)
sumDivM() - Return amount of numbers which divides m without remainder. - O(1)
equi(k) - find number x, where (x-k) divides m without remainder. return FALSE if there is no such number. - O(log(min(m,n)))
pairDivM() - Return TRUE iff the data structure contains pair of numbers that their sum divides m without remainder, FALSE otherwise. - O(1)

n is the number of elements currently at the structure.

I thought of AVL tree - where Init, insert and delete are ok with the run time restriction.
for sumDivM i will have a int field, which will increase by 1 everytime we insert a number which divides m without remainder (insert function will check this). this way i can return the amount by O(1).
for equi(k) and pairDivM() - i could not find a solution without running on the tree which is prohibited because of runtime. Any Ideas?

Answer 1

First of all notice that, given a number x, you really only care about x mod m, so you might as well calculate that and use that as a key to enter x into the AVL tree, which is acting as a map with key (x mod m) and value a set of numbers which are all equal to x, mod m.

For equi(k), just look up (-k mod m).

For pairDivM(), when you enter a number x into the data structure, look up the size of the set for (-x mod m) because for all of these numbers you are creating a new pair of numbers such that (x + y) = 0 mod m. You can answer pairDivM() at O(1) cost if you maintain a count of how many such pairs there are, modifying it when you insert and delete numbers.

For the other operations, I think either you've covered them or they are fairly obvious given that you have an AVL tree for (x mod m).