概要
{ 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; }