364A.md (1166B)
1 Source: https://codeforces.com/problemset/problem/364/A 2 3 A. Matrix 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 You have a string of decimal digits *s*. Let's define *b**ij* = *s**i*·*s**j*. Find in matrix *b* the number of such rectangles that the sum *b**ij* for all cells (*i*, *j*) that are the elements of the rectangle equals *a* in each rectangle. 22 23 A rectangle in a matrix is a group of four integers (*x*, *y*, *z*, *t*) (*x* ≤ *y*, *z* ≤ *t*). The elements of the rectangle are all cells (*i*, *j*) such that *x* ≤ *i* ≤ *y*, *z* ≤ *j* ≤ *t*. 24 25 Input 26 27 The first line contains integer *a* (0 ≤ *a* ≤ 109), the second line contains a string of decimal integers *s* (1 ≤ |*s*| ≤ 4000). 28 29 Output 30 31 Print a single integer — the answer to a problem. 32 33 Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier. 34 35 Examples 36 37 Input 38 39 ``` 40 10 41 12345 42 ``` 43 44 Output 45 46 ``` 47 6 48 ``` 49 50 Input 51 52 ``` 53 16 54 439873893693495623498263984765 55 ``` 56 57 Output 58 59 ``` 60 40 61 ```