yukicoder : No.1632 Sorting Integers (GCD of M)

シリーズもの。
https://yukicoder.me/problems/no/1632

問題

正整数の集合を考える。
この集合に含まれる整数は、1～9の各数字が含まれる回数が指定されたものに一致するもの全通りである。
この集合内の全整数におけるGCDを求めよ。

解法

1種類の数字しか使えない場合、集合に含まれる整数は1通りなので、その値を答える。
そうでない場合、末尾2桁の数字i,jを入れ替えると、その値は9(i-j)だけ変化することになる。

なので、集合中に含まれる適当な1つの値を求めたうえで、使用可能な2数字i,jにおける9(i-j)とのGCDを取れが良いことになる。
先に9(i-j)全通りのGCDを取っておくとよい。

int N;
int C[10];
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2, ll mo=mo) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,9) {
		cin>>C[i+1];
		if(C[i+1]==N) {
			ll v=(modpow(10,N)+mo-1)*modpow(9)*(i+1)%mo;
			cout<<v<<endl;
			return;
		}
	}
	int g=0;
	FOR(x,9) FOR(y,x) if(C[x+1]&&C[y+1]) g=__gcd(g,x-y);
	
	ll v=0;
	FOR(i,9) {
		ll a=(modpow(10,C[i+1],81*g)-1)*(i+1)%(81*g);
		v=(v*modpow(10,C[i+1],81*g)+a)%(81*g);
	}
	v=__gcd(v,81LL*g);
	cout<<v/9<<endl;
	
}

まとめ

シンプルな問題設定。