# 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!

## 算法分析

• 引理 $\forall a \le b, \; (a, b) \mid b-a$。

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const L = 15;
static int const M = 10000005;
char s[L];
int top, cnt, cc, p[M];
long long v[26], dv[L], dc[L], ans[M];

long long get_gcd(long long a, long long b) {
for (long long c; b; c = a % b, a = b, b = c)
;
return a;
}

void init() {
top = 0;
for (int i = 2; i < M; ++i) {
if (!p[i])
p[top++] = i;
for (int j = 0; j < top; ++j) {
int k = i * p[j];
if (k >= M)
break;
p[k] = 1;
if (!(i % p[j]))
break;
}
}
}

void dfs(int t, long long v) {
if (t == cnt)
return void(ans[cc++] = v);
for (int i = 0; i <= dc[t]; ++i, v *= dv[t])
dfs(t + 1, v);
}

int main() {
int n;
scanf("%d", &n), init();
for (int _ = 1; _ <= n; ++_) {
printf("Case %d:", _), scanf("%s", s);
int len = strlen(s), st = 0;
for (int c = 0; c < 26; ++c) {
v[c] = 0;
for (int i = 0; i < len; ++i) {
v[c] *= 10;
if (s[i] == c + 'a')
++v[c];
}
st += v[c] > 0;
}
long long gcd = 0;
if (st < 10)
for (int i = 0; i < 26; ++i)
gcd = get_gcd(gcd, v[i]);
else {
int k = 0;
for (int i = 0; i < 26; ++i)
if (v[i])
gcd += k++ * v[i];
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j)
if (v[i] && v[j] && v[i] < v[j])
gcd = get_gcd(gcd, v[j] - v[i]);
}
cnt = cc = 0;
for (int i = 0; i < top && 1ll * p[i] * p[i] <= gcd; ++i)
if (!(gcd % p[i])) {
dv[cnt] = p[i], dc[cnt] = 0;
for (; !(gcd % p[i]);)
gcd /= p[i], ++dc[cnt];
++cnt;
}
if (gcd > 1)
dv[cnt] = gcd, dc[cnt] = 1, ++cnt;
dfs(0, 1), std::sort(ans, ans + cc);
for (int i = 0; i < cc; ++i)
printf(" %lld", ans[i]);
puts("");
}
return 0;
}


418 I'm a teapot