Sebi and the equation 2
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sebi's father gives him a maths question every night after dinner which he has to solve before sleeping. Today's question is as follows.
There are four integers A, B, C, N. Consider the following equation in two non-negative integer variables x and y
x * y = (x | y) * (x & y) + A * x + B * y + C
Sebi's father asks him to consider solutions such that x, y don't exceed N. Let X be the sum of x's for all solutions (x, y) and Y be the sum of y's for all solutions (x, y).
Its already very late in night. He is very sleepy, he thinks that if you can help him in telling the answer of the problem, he will just tell the answer to his father and sleep. Can you please help him?
The first line of the input contains an integer T denoting the number of test cases.
Each of the next T lines contains four space separated integers, denoting A, B, C, N as defined in the statement.
Output a T line containing two space separated integers X and Y.
- 1 ≤ T ≤ 60
- 1 ≤ N ≤ 100000
- 1 ≤ A, B, C ≤ 10000
Input: 1 1 1 4 9 Output: 12 12
Input: 1 1 1 3 5 Output: 7 7
There are two solutions - (3, 9) and (9, 3). For example, (9, 3) is a solution because: 9 | 3 = 11 and 9 & 3 = 1, so 9 * 3 = 11 * 1 + 1 * 9 + 1 * 3 + 4.
The value of X will be 3 + 9 = 12, and where Y will be 9 + 3 = 12.
The solutions of the equation is (2, 5) and (5, 2). So, X = 7 and Y = 7.
|Tags||bitwise cook76 iscsi medium-hard sieve|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.