SubmultiplesOfN
SRM 805 · 2021-05-06 · by misof
Problem Statement
The number X appears in the number Y if, when written in base-10, the digits of X form a (not necessarily contiguous) subsequence of the digits of Y. For example, X = 246 appears in Y = 1234567 and X = 222 appears in Y = 222. On the other hand, the numbers 1223 and 31 do not appear in the number 123.
Given a
Constraints
- B will have between 1 and 5,000 characters, inclusive.
- Each character of B will be a digit.
- B will not start with a zero.
- N will be between 1 and 1,000, inclusive.
"1111111111" 7 Returns: 1
The only positive integer multiple of 7 that appears in the given number is 111,111. Note that we are counting distinct numbers, not their appearances: even though 111,111 can be seen in B in many different ways, we only want to count it once.
"12345678" 2 Returns: 170
Exactly 170 distinct even numbers appear in 12345678. Some of those numbers are 4, 1346 and 12345678.
"1357913579135791357913579" 2 Returns: 0
"1122334455" 6 Returns: 20
Four of these 20 numbers are 12, 114, 2244 and 1123344.
"1020402" 24 Returns: 6
The six multiples of 24 that appear in 1020402 are 24, 120, 240, 1200, 2040, and 10200.
"123456789012345678901234567890" 1 Returns: 62224120
Don't forget to calculate the answer modulo 10^9 + 7.
Submissions are judged against all 17 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubmultiplesOfN with a public method int count(string B, int N) · 17 test cases · 2 s / 256 MB per case