We keep dividing *l* by *k* until *l* is not a multiple of *k* any more, and then check whether *l* is reduced to 1 or not.

As *n* is limited up to 16, we can use bitmask to enumerate all the feasible combinations and check whether they can form a group or not. The total complexity is *O*(2^{n} × *n*^{2}).

This is a straightforward implementation problem. For each given string, we need to check the following conditions.

1) all the words end with the required suffix

2) all the words have the same gender

3) all the words appear in the required order

4) there is exactly one noun word

The idea is to previously calculate all the positions of the required prefix and suffix. Then, we enumerate every pair of feasible combination, and find out all the different substrings.

Therefore, the main task is how to determine whether two strings are the same or not. I did not come up with a good solution, however I studied the other accepted codes.

I found that they adopt an “unsigned long long int” variable *x*, initialized with zero value, and compute *x* = *x* × *prime* + *s*[*i*], where *prime* is a prime integer. I think this means to transform or map the string to an integer, like hash table. However, I did not figure out how could this guarantee that no two strings are mapped to the same integer, since we have at most 26^{2000} different strings but only 2^{64} integers. Although for some substring of length *m*, we can in fact only have *O*(*n*) different ones, which is quite small compared with 2^{64}, but this still can not guarantee that no collisions occur...

There is a standard solution, referred to as “sieve function”, to this problem. Using “bitset” can also solve the memory problem. Instead of testing each prime integer, we can enumerate *a* and *b*, and then test whether the result of *a*^{2} + *b*^{2} is prime or not. The complexity is *O*(*ab*) = *O*(*n*). To further decrease the constant of complexity, for each value of *a*, we can start enumerating the value of *b* from *a* + 1, with increment step of 2. The reason is that if both *a* and *b* are even or odd, the value of *a*^{2} + *b*^{2} must be an even integer, and thus is definitely not a prime integer.