SRM 375 250pt: DivisibleByDigits

TopCoder

問題概要

整数n(<10^9)が与えられる。nがprefixになるような数のうち、nの各桁の数字(0以外)で割りきれるような最小のものを返す問題。

考えたこと

  • とりあえずLCMが必要なことは分かる。
  • LCMが分かれば後はnがprefixになるような数字の上限と下限の間にLCMの倍数があるか判定すれば良い。
  • sup/LCM > inf/LCMならばその間にLCMの倍数が存在するので、それを真面目に実装する。
  • 合わない。何で？
  • 問題文読み間違えてた。答えはnの倍数でもある必要があると思っていたけど、そうじゃないらしい。
  • 修正。Accept。

practiceで通ったコード

計算量O(log N)くらい。

#include <algorithm>
using namespace std;

typedef long long  int64;

int64 lcm(int64 a, int64 b){
	return a/__gcd(a,b)*b;
}

struct DivisibleByDigits {

	int64 getContinuation(const int64 n) {
		int64 A = 1;
		for(int64 m=n; m>0; m/=10){
			int64 last_dig = m%10;
			if(last_dig){
				A = lcm(A, last_dig);
			}
		}

		if(n%A==0){
			return n;
		}

		for(int64 d=10;;d*=10){
			int64 lb = n*d, ub = (n+1)*d-1;
			if(lb%A==0){
				return lb;
			}
			if(lb/A < ub/A){
				return ((lb+A-1)/A)*A;
			}
		}
		return -1;
	}

};

他の人の解法

りんごさんの解法が相変わらずシンプルだった。答えはn*10^d + iの形になるけど、LCM(1..9)が4桁程度なので、dの値は高々5程度。なので単純に全探索すれば良い。

#include <vector>
using namespace std;

typedef long long  int64;

vector<int> digs;

struct DivisibleByDigits {

	int64 getContinuation(const int64 n) {
		for(int64 m=n; m; m/=10){
			int dig = m%10;
			if(dig){
				digs.push_back(dig);
			}
		}

		for(int d=0, base=1; d<5; d++, base *= 10){
			for(int i=0; i<base; i++){
				if(check(n*base + i)){
					return n*base + i;
				}
			}
		}

		return -1;
	}

	bool check(int64 x){
		for(int i=0; i<(int)digs.size(); i++){
			if(x%digs[i]){
				return false;
			}
		}
		return true;
	}
};