182D.md (1323B)
1 Source: https://codeforces.com/problemset/problem/182/D 2 3 D. Common Divisors 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Vasya has recently learned at school what a number's divisor is and decided to determine a string's divisor. Here is what he came up with. 22 23 String *a* is the divisor of string *b* if and only if there exists a positive integer *x* such that if we write out string *a* consecutively *x* times, we get string *b*. For example, string "abab" has two divisors — "ab" and "abab". 24 25 Now Vasya wants to write a program that calculates the number of common divisors of two strings. Please help him. 26 27 Input 28 29 The first input line contains a non-empty string *s*1. 30 31 The second input line contains a non-empty string *s*2. 32 33 Lengths of strings *s*1 and *s*2 are positive and do not exceed 105. The strings only consist of lowercase Latin letters. 34 35 Output 36 37 Print the number of common divisors of strings *s*1 and *s*2. 38 39 Examples 40 41 Input 42 43 ``` 44 abcdabcd 45 abcdabcdabcdabcd 46 ``` 47 48 Output 49 50 ``` 51 2 52 ``` 53 54 Input 55 56 ``` 57 aaa 58 aa 59 ``` 60 61 Output 62 63 ``` 64 1 65 ``` 66 67 Note 68 69 In first sample the common divisors are strings "abcd" and "abcdabcd". 70 71 In the second sample the common divisor is a single string "a". String "aa" isn't included in the answer as it isn't a divisor of string "aaa".