概要
次のようなクエリ ( n, l, r ) を t ( ≦ 1,000 ) 個処理せよ
- クエリ ( n, l, r ) := n を [ l, r ] に含まれる整数の和として表現できるかどうか判定し、"Yes" / "No" で示せ
解法
n, l, r の値がかなり大きくなり得るので、ある程度効率的な方法を考える必要があります。
[ l, r ] に含まれる整数 k 個の和は区間 [ kl, kr ] に収まります。逆に [ kl, kr ] 内に n を含むような k が存在すれば、クエリの答えは "Yes" であると分かります。そのような k が存在するとすれば、そのときの k は n を r で切り上げ整数除算した結果と一致します。そうして求まった k について、条件式
- k * l <= n && n <= k * r
を評価した結果が、クエリの答えとなります。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) bool solve( const int n, const int l, const int r ) { const int k = ( n + r - 1 ) / r; return k * l <= n && n <= k * r; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int t; cin >> t; REP( i, 0, t ) { int n, l, r; cin >> n >> l >> r; cout << ( solve( n, l, r ) ? "Yes" : "No" ) << endl; } return 0; }