AtCoder Beginner Contest 220

##[A - Find Multiple](https://atcoder.jp/contests/abc220/tasks/abc220_a)

O(N)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int A, B, C;
    cin >> A >> B >> C;
 
    for(int i=0; i<=1000; i++){
        if(A<=C*i && C*i<=B){
            cout << C*i << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
 
    return 0;
}
```

##[B - Base K](https://atcoder.jp/contests/abc220/tasks/abc220_b)

O(N)
N進数を１０進数への変換は、
各桁の重みと数値の掛け算。

K^i　＊　A_i
K^i　＊　B_i

で求めることができます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int K;
    string A, B;
    cin >> K >> A >> B;

    ll AA=0;
    for(int i=0; i<A.size(); i++){
        AA += pow(K, i) * (A[A.size()-i-1]-'0');
    }
    ll BB=0;
    for(int i=0; i<B.size(); i++){
        BB += pow(K, i) * (B[B.size()-i-1]-'0');
    }

    cout << AA * BB <<  endl;

    return 0;
}
```

##[C - Long Sequence](https://atcoder.jp/contests/abc220/tasks/abc220_c)

O(N)
全探索を行うとTLEになります。
X / Aの配列の要素の合計 = Xを超えるまでに必要な配列Aの数 
を行うと必要な配列Aの数をO(１)で求めることができ計算量を減らせます。
あとは必要なAの要素をシミュレートすると答えがでます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, X;
    cin >> N;

    queue<ll> A;
    ll total=0;
    rep(i, N){
        ll a;
        cin >> a;
        A.push(a);
        total+=a;
    }

    cin >> X;
    ll sum=(X/total)*total;
    ll res=(X/total)*A.size();
    while(sum<=X){
        ll a = A.front();
        A.pop();

        sum += a;
        res++;
        A.push(a);
    }
    cout << res << endl;

    return 0;
}
```

##[D - FG operation](https://atcoder.jp/contests/abc220/tasks/abc220_d)

O(N*10)

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dp[100010][10];

int main() {
    ll N;
    cin >> N;
   
    vector<ll> A(N+1);
    for(int i=1; i<=N; i++) cin >> A[i];

    dp[1][A[1]%10]=1;

    for(int i=1; i<N; i++){
        for(int j=0; j<10; j++){
            dp[i+1][(j+A[i+1])%10] = (dp[i+1][(j+A[i+1])%10] + dp[i][j]) % 998244353;
            dp[i+1][(j*A[i+1])%10] = (dp[i+1][(j*A[i+1])%10] + dp[i][j]) % 998244353;
        }
    }

    rep(i, 10) cout << dp[N][i] << endl;

    return 0; 
}
```