yukicoder No443 GCD of Permutation
考察
まず愚直に整数の各桁を並べ替えて出来る整数の集合を列挙することは制約から無理ということが分かる。
ここから公式解説の解法について考える(自分に向けての補足)
Sに含まれる整数"xxxxab"と"xxxxba"(である)を考える。この時、この2つの値の差はになる。
このというのは
例えば、"12ab","12ba"という2つの整数があるとすると上2桁の数値は意識しないで良くて,
"ab" - "ba"を考えるとになる。
つまり、とすると先程の式はになり
という風に考えることができる。
今回求める最大公約数はの約数であると考えられる。
@tookunn_1213 ということは a > bと考えると(xxxxab - xxxxba)の差9(a - b)はxxxxabとxxxxbaの最大公約数の倍数になる ということか
— tookunn (@tookunn_1213) 2016年11月12日
考えられるのすべての組み合わせの最大公約数との最大公約数を求めると今回求めるべき最大公約数Gとなる。
ソースコード
def gcd(x,y): return x if y == 0 else gcd(y,x%y) N = input() n = int(N) s = set(map(int,list(N))) if len(s) == 1: print(N) else: G = 0 for i in s: for j in s: if i < j: if G == 0: G = 9 * (j - i) else: G = gcd(G,9 * (j - i)) div = set() i = 1 while i * i <= G: if G % i == 0: div.add(i) div.add(G//i) i+=1 div = list(div) div.sort() div.reverse() for d in div: if n % d == 0: print(d) break