AtCoder Beginner Contest 215

##[A - Your First Judge](https://atcoder.jp/contests/abc215/tasks/abc215_a)

O(1)

```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() {
    string s;
    cin >> s;

    if("Hello,World!" == s) cout << "AC" << endl;
    else cout << "WA" << endl;

    return 0;
}
```

##[B - log2(N)](https://atcoder.jp/contests/abc215/tasks/abc215_b)

O(N)
long long型の累乗はpowlです。

```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;
    cin >> N;

    ll res=0;
    for(int i=1; i<=N; i++){
        if(powl(2, i) > N) break;
        else res = i;
    }

    cout << res << endl;

    return 0;
}
```


##[C - One More aab aba baa](https://atcoder.jp/contests/abc215/tasks/abc215_c)

O(N)
辞書順の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() {
    string s;
    int k;
    cin >> s >> k;

    sort(s.begin(), s.end());

    int cnt=0;
    do {
        cnt++;
        if(cnt == k){
            cout << s << endl;
            break;
        }
    } while (next_permutation(s.begin(), s.end()));

    return 0;
}
```

##[D - Coprime 2](https://atcoder.jp/contests/abc215/tasks/abc215_d)

O()
素因数分解とエラトスネテスの篩の応用です。
gcd(A[i], k) == 1の条件を満たすとは、A[i]の約数の倍数以外と読めます。
gcd(6, 3) = 3になりますね。

A[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; }
 
bool dp[100000];
set<int> ret;
 
void divisor(int n) {
    int m=n, l=2;
    while(l*l<=m){
        if(m%l==0){
            ret.insert(l);
            m=m/l;
        }else{
            l++;
        }
    }
    ret.insert(m);
}
 
int main() {
    ll N, M;
    cin >> N >> M;
 
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
 
    for(int i=0; i<N; i++){
        if(A[i]==1) continue;
        divisor(A[i]);
    }

    for(auto& itr:ret){
        for(int i=itr; i<=M; i+=itr){
            dp[i] = true;
        }
    }

    vector<int> res;
    for(int i=1; i<=M; i++){
        if(dp[i]) continue;
        res.push_back(i);
    }
    sort(res.begin(), res.end());
 
    cout << res.size() << endl;
    rep(i, res.size()) cout << res[i] << endl; 
 
    return 0;
}
```