AnArray
SRM 668 · 2015-08-31 · by zxqfl
SRM 668 · 2015-08-31 · by zxqfl · Math
Problem Statement
Problem Statement
One day, Bob the Coder was wondering whether abstract programming problems can have applications in practice. The next day, he was selected to be on a quiz show. He will win one million dollars if he answers the following question:
Given aint[] A with N elements and an int K, count the number of tuples (p, q, r) such that 0 <= p < q < r < N and A[p] * A[q] * A[r] is divisible by K.
Please compute and return the answer to Bob's question.
Given a
Please compute and return the answer to Bob's question.
Constraints
- A will contain between 3 and 2,000 elements, inclusive.
- K will be between 1 and 1,000,000, inclusive.
- Each element of A will be between 1 and 100,000,000, inclusive.
Examples
0)
{31, 1, 3, 7, 2, 5}
30
Returns: 1
The return value is 1 because there is exactly one valid tuple. The tuple is (2, 4, 5). It is valid because A[2] * A[4] * A[5] = 3 * 2 * 5 = 30.
1)
{4, 5, 2, 25}
100
Returns: 2
2)
{100000000, 100000000, 100000000}
1000000
Returns: 1
Note that the product A[p] * A[q] * A[r] doesn't have to fit into a 64-bit integer variable.
3)
{269, 154, 94, 221, 171, 154, 50, 210, 258, 358, 121, 159, 8, 47, 290, 125, 291, 293, 338, 248, 295, 160, 268, 227, 99, 4, 273}
360
Returns: 114
4)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
1
Returns: 220
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AnArray with a public method int solveProblem(vector<int> A, int K) · 61 test cases · 2 s / 256 MB per case