LeetCode Biweekly Contest 143 : 3348. Smallest Divisible Digit Product II

これは難易度8でもいいかも。
https://leetcode.com/problems/smallest-divisible-digit-product-ii/description/

問題

最大200000桁の整数Nと、正整数Tが与えられる。
N以上の整数のうち、各桁の積がTの倍数である最小値が存在するなら答えよ。

解法

Tを素因数分解したとき、2,3,5,7以外がある場合は存在しない。
そうでない場合、下の桁から順にみて行って、「今見ている桁がNより大きいとしたとき、その下の値に2,3,4,5,6,7,8,9を詰めてTの倍数にできるか」を見て行けばよい。
その際、できるため1の位に近い方に大きな数字を入れるように使用。
Tの素因数は高々2^50もないので、Nのうち下20桁ぐらいまで見れば条件を満たす整数が見つかる。

vector<int> D[10];
int C[10];

string get(vector<int> V) {
	string S;
	int i;
	FOR(i,V[7]) S+="7";
	FOR(i,V[5]) S+="5";
	FOR(i,V[3]/2) S+="9";
	FOR(i,V[2]/3) S+="8";
	V[3]%=2;
	V[2]%=3;
	if(V[3]>0&&V[2]>0) S+="6", V[3]--,V[2]--;
	if(V[3]==1) S+="3", V[3]--;
	if(V[2]==2) S+="4", V[2]-=2;
	if(V[2]==1) S+="2", V[2]-=1;
	return S;
	
}

class Solution {
public:
    string smallestNumber(string num, long long t) {
		int i,j,x;
		for(i=2;i<=9;i++) {
			D[i].clear();
			j=i;
			for(x=2;x<=i;x++) while(j%x==0) D[i].push_back(x), j/=x;
		}
		vector<int> C(10);
		for(i=2;i<=9;i++) while(t%i==0) C[i]++,t/=i;
		if(t>1) return "-1";
		
		FOR(i,num.size()) {
			if(num[i]=='0') {
				for(;i<num.size();i++) {
					num[i]='1';
				}
				break;
			}
		}
		FORR(c,num) FORR(a,D[c-'0']) C[a]--;
		
		if(get(C)=="") return num;
		reverse(ALL(num));
		num+="0000000000000000000000000000000000000000000";
		int N=num.size();
		FOR(i,N) {
			FORR(a,D[num[i]-'0']) C[a]++;
			for(x=num[i]-'0'+1;x<=9;x++) {
				FORR(a,D[x]) C[a]--;
				string T=get(C);
				if(T.size()<=i) {
					while(T.size()<i) T+="1";
					sort(ALL(T));
					reverse(ALL(T));
					num[i]='0'+x;
					FOR(x,i) num[x]=T[x];
					while(num.back()=='0') num.pop_back();
					reverse(ALL(num));
					return num;
				}
				FORR(a,D[x]) C[a]++;
			}
		}
		return "";
        
    }
};

まとめ

難しくはないけどちょっとめんどい。