ARC052 D - 9

問題ページ

と表す。 は下から 桁目の値であり、 である。 となるような を求めたい。

の組は 通り存在するため、普通に全列挙するとTLEしてしまう。そこで半分全列挙を行う。 と についてそれぞれ和を列挙する。足したときに で0になるようなものが何個あるのか求めればよい。

上限 の設定から を列挙するのが多少面倒になっているが、上位部分が と一致するか？の場合分けをすればよい。

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll k, m;  
    cin >> k >> m;  
  
    auto calc = [&](ll n, bool islower) -> ll {  
        ll t = n, ret = 0, pw = (islower ? 1 : 100000%k);  
        REP(i, 5) {  
            ret += (t%10)*(pw-1)%k;  
            (pw *= 10) %= k;  
            t /= 10;  
        }  
        return (ret%k+k)%k;  
    };  
  
    ll ans = 0;  
    {  
        map<ll,ll> cnt;  
        REP(i, 100000) cnt[calc(i, true)]++;  
        REP(i, m/100000) {  
            ll val = calc(i, false);  
            ans += cnt[(k-val)%k];  
        }  
    }  
    {  
        map<ll,ll> cnt;  
        REP(i, m%100000+1) cnt[calc(i, true)]++;  
        ans += cnt[(k-calc(m/100000, false))%k];  
    }  
    cout << ans-1 << endl;  
  
    return 0;  
}  

半分全列挙見えなかった…
数字和と元の数字の一致、 進数のときに するくらいしか性質を知らない(なんかあるのかな？)ので、これでだめなら全探索ベースで考えるとかした方がいいのかも…？