codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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".