ModuloFourDivisor
Member SRM 458 · 2009-12-03 · by rng_58
Member SRM 458 · 2009-12-03 · by rng_58 · Math
Problem Statement
Problem Statement
A quadruplet of non-negative integers (a,b,c,d) is called a divisor quadruplet if there exists at least one positive integer N that satisfies the following four conditions:
long[] s A, B, C and D. Return the number of divisor quadruplets (a,b,c,d) such that A contains a, B contains b, C contains c and D contains d.
- N has exactly a divisors x such that x ≡ 0 (mod 4).
- N has exactly b divisors x such that x ≡ 1 (mod 4).
- N has exactly c divisors x such that x ≡ 2 (mod 4).
- N has exactly d divisors x such that x ≡ 3 (mod 4).
Notes
- x ≡ k (mod 4) means (x - k) is divisible by 4.
Constraints
- A, B, C and D will contain between 1 and 50 integers, inclusive.
- Each element of A, B, C and D will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- A, B, C and D will contain no duplicate elements.
Examples
0)
{1}
{1}
{1}
{0}
Returns: 1
(1, 1, 1, 0) is a divisor quadruplet because N = 4 satisfies the conditions.
1)
{0}
{0}
{0}
{0}
Returns: 0
All integers have at least one divisor.
2)
{0}
{0,1}
{0}
{0}
Returns: 1
(0, 0, 0, 0) is not a divisor quadruplet. (0, 1, 0, 0) is a divisor quadruplet.
3)
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
Returns: 818
4)
{1000000000000000000,999999999999999999,999999999999999998,999999999999999997,999999999999999996,999999999999999995,999999999999999994,999999999999999993,999999999999999992,999999999999999991,999999999999999990,999999999999999989,999999999999999988,999999999999999987,999999999999999986,999999999999999985,999999999999999984,999999999999999983,999999999999999982,999999999999999981,999999999999999980,999999999999999979,999999999999999978,999999999999999977,999999999999999976,999999999999999975,999999999999999974,999999999999999973,999999999999999972,999999999999999971,999999999999999970,999999999999999969,999999999999999968,999999999999999967,999999999999999966,999999999999999965,999999999999999964,999999999999999963,999999999999999962,999999999999999961,999999999999999960,999999999999999959,999999999999999958,999999999999999957,999999999999999956,999999999999999955,999999999999999954,999999999999999953,999999999999999952,999999999999999951}
{1000000000000000000,999999999999999999,999999999999999998,999999999999999997,999999999999999996,999999999999999995,999999999999999994,999999999999999993,999999999999999992,999999999999999991,999999999999999990,999999999999999989,999999999999999988,999999999999999987,999999999999999986,999999999999999985,999999999999999984,999999999999999983,999999999999999982,999999999999999981,999999999999999980,999999999999999979,999999999999999978,999999999999999977,999999999999999976,999999999999999975,999999999999999974,999999999999999973,999999999999999972,999999999999999971,999999999999999970,999999999999999969,999999999999999968,999999999999999967,999999999999999966,999999999999999965,999999999999999964,999999999999999963,999999999999999962,999999999999999961,999999999999999960,999999999999999959,999999999999999958,999999999999999957,999999999999999956,999999999999999955,999999999999999954,999999999999999953,999999999999999952,999999999999999951}
{1000000000000000000,999999999999999999,999999999999999998,999999999999999997,999999999999999996,999999999999999995,999999999999999994,999999999999999993,999999999999999992,999999999999999991,999999999999999990,999999999999999989,999999999999999988,999999999999999987,999999999999999986,999999999999999985,999999999999999984,999999999999999983,999999999999999982,999999999999999981,999999999999999980,999999999999999979,999999999999999978,999999999999999977,999999999999999976,999999999999999975,999999999999999974,999999999999999973,999999999999999972,999999999999999971,999999999999999970,999999999999999969,999999999999999968,999999999999999967,999999999999999966,999999999999999965,999999999999999964,999999999999999963,999999999999999962,999999999999999961,999999999999999960,999999999999999959,999999999999999958,999999999999999957,999999999999999956,999999999999999955,999999999999999954,999999999999999953,999999999999999952,999999999999999951}
{1000000000000000000,999999999999999999,999999999999999998,999999999999999997,999999999999999996,999999999999999995,999999999999999994,999999999999999993,999999999999999992,999999999999999991,999999999999999990,999999999999999989,999999999999999988,999999999999999987,999999999999999986,999999999999999985,999999999999999984,999999999999999983,999999999999999982,999999999999999981,999999999999999980,999999999999999979,999999999999999978,999999999999999977,999999999999999976,999999999999999975,999999999999999974,999999999999999973,999999999999999972,999999999999999971,999999999999999970,999999999999999969,999999999999999968,999999999999999967,999999999999999966,999999999999999965,999999999999999964,999999999999999963,999999999999999962,999999999999999961,999999999999999960,999999999999999959,999999999999999958,999999999999999957,999999999999999956,999999999999999955,999999999999999954,999999999999999953,999999999999999952,999999999999999951}
Returns: 0
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ModuloFourDivisor with a public method int countQuadruplets(vector<long long> A, vector<long long> B, vector<long long> C, vector<long long> D) · 98 test cases · 2 s / 256 MB per case