Give two positive integer a,b (1<=a<=30, 1<=b<=10000000) ,and define two unrepeatable set L and R,
L = {x * y | 1 <= x <= a, 1 <= y <= b, x,y is integer}
R = {x ^ y | 1 <= x <= a, 1 <= y <= b, x,y is integer},
^ is XOR operate
For any two integer: A∈L, B∈R, we format B to n+1(n is the decimal digit number of b) decimal digit(fill 0 in front of B),and then joint B to the end of A and get a new integer AB.
Compute the sum of all generated integer AB (In case the sum exceed, just return "sum mod 1000000007", mod means modular operation)
Note: the time of your algorithm is no more than 3 seconds
My algorithm is very simple:we can easily get the max number in set R, and the element in R is 0,1,2,3...maxXor,(the element max(a,b) may be not in R), using a hash table the compute set L. But the algorithm consume 4 seconds when a = 30, b = 100000.
Give an example:
a = 2, b = 4, so
L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} = {1, 2, 3, 4, 6, 8}
R = {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} = {0, 1, 2, 3, 5, 6}
All generated integer AB is:
{
100, 101, 102, 103, 105, 106,
200, 201, 202, 203, 205, 206,
300, 301, 302, 303, 305, 306,
400, 401, 402, 403, 405, 406,
600, 601, 602, 603, 605, 606,
800, 801, 802, 803, 805, 806
}
The sum of all AB is 14502