Paint the Ceiling

Problem Overview

• Count how many square/rectangular house configurations use lengths from a generated set s with area ≤ a.
• Input: s0, n, k, b, m generate n lengths by s_i = ((k*s_{i-1}+b) mod m) + 1 + s_{i-1}; a is the area cap. Output: a long integer count.
• Constraints: n ≤ 6×10^6, s_i ≤ 10^9, k,b,m ≤ 10^9, a ≤ 10^18.
• Real-world: choose dimensions eligible for a free ceiling paint promotion; asked in Snowflake interviews, a coding interview problem and interview question.