tookunn’s diary

主に競技プログラミング関係

yukicoder No443 GCD of Permutation

考察

まず愚直に整数Nの各桁を並べ替えて出来る整数の集合Sを列挙することは制約から無理ということが分かる。

ここから公式解説の解法について考える(自分に向けての補足)

yukicoder


Sに含まれる整数"xxxxab"と"xxxxba"(a > bである)を考える。この時、この2つの値の差は9(a - b)になる。

この9(a - b)というのは
例えば、"12ab","12ba"という2つの整数があるとすると上2桁の数値は意識しないで良くて,
"ab" - "ba"を考えると((a - b) * 10 + b - a)になる。
つまり、c = a - bとすると先程の式はc * 10 - cになり
9 * c = 9(a - b)という風に考えることができる。

今回求める最大公約数G9(a - b)の約数であると考えられる。


考えられる9(a - b)のすべての組み合わせの最大公約数とNの最大公約数を求めると今回求めるべき最大公約数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