Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-13SRM375 (Practice)

SRM 375 DivisibleByDigits

|  SRM 375 DivisibleByDigits - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 375 DivisibleByDigits - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8318

  • 数論ゲーきたこれ
    • 割るべき数は1〜9のどれかだから、まず出現する数字のLCMを求めてしまおう
  • 方針を考える
    • 初期状態で割り切れればそれで終了
    • そうでなければ、数字を1つずつ追加していくとして・・・
      • 10^a倍すると、残り必要な数も自動的に分かるから、それが0〜(10^a-1)に収まってるかで判定すればよさそう
  • 書けた。サンプル通った。
    • 小さめの数で変なことが起こらないか確認する。
    • 大丈夫。
  • 出した
public class DivisibleByDigits {
	public long lcm(long a, long b) {
		long g = gcd(a, b);
		return a * b / g;
	}
	
	public long gcd(long a, long b) {
		return (b != 0) ? gcd(b, a%b) : a;
	}
	
	public long getContinuation(int n) {
		String l = String.valueOf(n);
		int len = l.length();
		long d = 1;
		for (int i = 0 ; i < len ; i++) {
			int z = l.charAt(i) - '0';
			if (z >= 1) {
				d = lcm(d, z);
			}
		}
		System.out.println(d);
		if (n % d == 0) {
			return n;
		}
		long ln = n;
		for (int ad = 1 ; ad <= 15 ; ad++) {
			long df = (ln * (long)Math.pow(10, ad)) % d;
			long maxadd = (long)Math.pow(10, ad) - 1;
			if (df == 0) {
				return (ln * (long)Math.pow(10, ad));
			} else if ((d - df) <= maxadd) {
				return (ln * (long)Math.pow(10, ad)) + (d - df);
			}
		}	
		return 0;
	}
}