Divisibility
题目描述
Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!
One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.
Here is what he wrote in his textbook about the string ‘lalala’:
- it can be transformed to an $282828$ by mapping ‘l’ to $2$, and ‘a’ to $8$,
- it can also be transformed to $909090$ by mapping ‘l’ to $9$, and ‘a’ to $0$,
- acouple of examples of invalid transformations are $050505$ (the resulting number has a leading zero), $333333$ (different letters are mapped to the same digit), $123456$ (no mapping to the original letters at all).
But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn’t even imagine that all numbers produced by the same string pattern might have common properties!
For example, every single number that can be produced from string ‘lalala’ is always divisible by $259$, irrespective of the letter-to-digit mapping you choose. Fascinating!
So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.
As usual, the King desperately wants you to help him, so stop thinking and start acting!
题意概述
给定一个字符集大小不超过$10$的字符串$s$。定义一个数字是合法的，当且仅当它没有前导零，位数等于$|s|$，且它从高到低的第$i$位和第$j$位相等当且仅当$s_i=s_j$。求出所有能整除每一个合法数字的数。有$n$组数据。
数据范围：$1 \le n \le 100, \ 1 \le |s| \le 14$。
算法分析
如果我们求出了所有合法数字的 GCD，那么答案就是 GCD 的所有约数。
为了方便，我们设字符串的下标从$1$开始。
令$g$等于所有合法数字的 GCD。首先考虑它的下界。假设字符$i$在字符串中出现的次数为$a_i$，出现的位置是$p_{i, 1}, p_{i, 2}, \ldots, p_{i, a_i}$。定义字符$i$的价值$v_i=\sum_{j=1}^{a_i} 10^{|s|-p_{i, j}}$。显然，所有合法的数字都可以被表示为$\sum k_iv_i$，其中$k_i$表示字符$i$变成的数字。所以，$g$的下界为$(v_a, v_b, \ldots, v_z)$。
考虑$g$的上界。分两种情况讨论。
- 引理 $\forall a \le b, \ (a, b) \mid b-a$。
当字符集大小小于$10$时，对于每一个$i$，总能找到一个合法的数$x$使得$x+v_i$也合法。这是因为总有一个合法的数包含$k_i$但不包含$k_i+1$。根据引理，$(x, x+v_i) \mid v_i$。由于$x$和$x+v_i$均合法，因此$g \mid (x, x+v_i)$，即$g \mid v_i$。所以，$g$的上界为$(v_a, v_b, \ldots, v_z)$。结合下界，$g=(v_a, v_b, \ldots, v_z)$。
当字符集大小等于$10$时，要将某个$k_i$加一就必须将另一个$k_j$减一。如果对于不同的$i, j$，有$v_i, v_j \gt 0 \land v_i \lt v_j$，那么$g \mid v_j-v_i$。令$S={v_j-v_i \mid v_i, v_j \gt 0 \land v_i \lt v_j}$。对于一个合法的数，它加上/减去$S$中的某些数后仍是一个合法的数；对于$S$中的数，存在一个合法的数加上/减去它之后仍是一个合法的数。即一个合法的数$x$与$S$中的数加减可以得到所有合法的数。令$h$等于$S$中所有数的 GCD，那么显然，$g$的下界为$(x, h)$。又因为$g \mid x$且$g$整除$S$中的所有数，所以$g$的上界也是$(x, h)$。即$g=(x, h)$。
求$g$的所有约数可以先分解质因数再 DFS。
代码
1 | |