torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #152, Division 2, B : Chilly Willy

概要

{ 2, 3, 5, 7 } の全てで割り切れる n 桁の整数で最も小さいものを出力せよ。
存在しない場合は -1 を出力せよ。

解法

2, 3, 5, 7 が互いに素であるので、求める数は 2 × 3 × 5 × 7 = 210 の倍数です。
従って、二桁以下では -1 、三桁では 210 になります。
一般の場合、最上位桁は 1 で、下位三桁は 50, 80, 170, 20, 200, 110 のいずれかで、これは周期性をもちます。
1 + 適当な数の 0 + 対応する下位桁 が答えです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

string sufs[] = { "50", "80", "170", "20", "200", "110" };

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	if ( n <= 2 )
	{
		cout << -1 << endl;
		return 0;
	}

	if ( n == 3 )
	{
		cout << 210 << endl;
		return 0;
	}

	cout << 1;

	REP( i, 0, n - sufs[ ( n - 4 ) % 6 ].size() - 1 )
	{
		cout << "0";
	}
	
	cout << sufs[ ( n - 4 ) % 6 ] << endl;

	return 0;
}