yukicoder : No.443 GCD of Permutation

今日は1問目以外グダグダでした。
http://yukicoder.me/problems/no/443

問題

大きな正整数Nが与えられる。
これらの桁を入れ替えて得られる全ての整数の最大公約数を求めよ。

解法

Nの各桁が全て同じ数字なら、Nを答える。
隣接する2つの桁の数値a,bを入れ替えた場合を考えると、その差は9*|a-b|の倍数になる。
(隣接していない場合、たとえばx桁離れている2つの数字を入れ替えた場合差は(10^x-1)*|a-b|の倍数であり、(10^x-1)が9の倍数なので結局これも9*|a-b|の倍数である)

よって、N中に登場する数字の対(a,b)に対し、9*|a-b|の最大公約数を求め、最後にN自体との最大公約数を求めればよい。

import sys
import math

def gcd(a, b):
	return a if b == 0 else gcd(b, a%b)

N = raw_input()
S = set()

for c in N:
	S.add(int(c))

if len(S) == 1:
	print N
else:
	G = 0
	for y in S:
		for x in S:
			if y > x:
				G = gcd(G, 9*(y-x))
	print gcd(int(N),G)

まとめ

本番嘘解法で通している…。