SRM504.5 Div1 Easy TheNumbersWithLuckyLastDigit

問題

問題文

整数 $n$ を， $1$ の位の数字が $4$ か $7$ の正整数の和で表したい． 表せるか判定し，表せるならそうするのに必要な数の最小値を求めなさい．

方針

ある $x$ が表すことができるとき，それを構成する Lucky Number のうち $1$ つを選んで $10k$ 足すと $x+10k$ も表すことができる．また， $7$ と $10$ は互いに素なので， $7$ の倍数を $10$ で割ったあまりの中には， $0$ から $9$ まで全て全て含まれる．したがって，ある程度より大きい数は， $10$ で割ったあまりだけを見て判断できる． 小さい場合も含めて， $4i+7j$ を全探索する．探索の範囲は広めにとる．

実装

class TheNumbersWithLuckyLastDigit {
public:
    int find(int N_) {
        ll N = N_;
        ll x = N%10;
        ll ans = 1e10;
        rep(i,50)rep(j,50)if(i+j){
            ll m = 4*i+7*j;
            ll y = m%10;
            if(N >= m && x==y) ans = min(ans, i+j);
        }
        if(ans == 1e10) ans = -1;
        return ans;
    }
};