AtCoder ABC 215 D

題目連結:AtCoder Beginner Contest 215: D – Coprime 2

題目敘述 :

給定 n, m 下一行會有 n 個數字,輸出所有k in 1~m,k是與所有數字皆互質的數。

範例輸入 1 :

3 12
6 1 5

範例輸出 1 :

3
1
7
11

題解 :

用埃氏篩法在log(n)的時間內做質因數分解,接著將所有數字的質因數聯集存在bitset中,最後判斷1~m的所有數字的質因數之中有無存於bitset中。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll N=100010;
#define IO_SPEEDUP ios::sync_with_stdio(0);cin.tie(0);
#define IO_INIT cout<<fixed<<setprecision(6);

int n,m;
int pri[N];
bitset<N> bt;

void init(){
    pri[1]=0;
    for(int i=2;i<N;++i){
        if(pri[i]==0){
            pri[i]=i;
            for(ll k=(ll)i*i;k<N;k+=i)
                pri[k]=i;
        }
    }
}

void div(int n){
    while(pri[n]>0){
        bt[pri[n]]=true;
        n/=pri[n];
    }
}

bool check(int n){
    while(pri[n]>0){
        if(bt[pri[n]]){
            return false;
        }
        n/=pri[n];
    }
    return true;
}

int main(){
    IO_SPEEDUP; IO_INIT;

    cin>>n>>m;
    init();

    for(int i=0;i<n;++i){
        int a;
        cin>>a;
        div(a);
    }

    vector<int> ans;
    for(int i=1;i<=m;++i){
        if(check(i)){
            ans.emplace_back(i);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<"\n";
    }
}

AtCoder ABC 215 C

題目連結:AtCoder Beginner Contest 215: C – One More aab aba baa

題目敘述 :

輸出 S 中字典順序第 K 大的排列.

範例輸入 1 :

aab 2

範例輸出 1 :

aba

範例輸入 2 :

ydxwacbz 40320

範例輸出 2 :

zyxwdcba

題解 :

用內建函式next_permutation()可以生成字典序大一點的排列。

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);

    string str;
    int n;

    cin>>str>>n;

//  因為沒有說輸入的會是字典序最小的,因此要先排序
    sort(str.begin(),str.end());
//  會是n-1是因為還沒進行前就是最小(第k=1小)
    for(int i=0;i<n-1;++i){
        next_permutation(str.begin(),str.end());
    }
    cout<<str;
}

AtCoder ABC 215 B

題目連結:AtCoder Beginner Contest 215: B – log2(N)

題目敘述 :

輸入正整數 N, 輸出最大整數 k 使 2^k≤N.

範例輸入 1 :

1000000000000000000

範例輸出 1 :

59

範例輸入 2 :

6

範例輸出 2 :

2

題解 :

用迴圈循環計算。 在整數運算時 ans<<=1 相當於 ans*=2

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    long long n;
    cin>>n;

    int ct=0;
    long long ans=1;
    while(ans*2<=n){
        ans<<=1;
        ct++;
    }
    cout<<ct;
}

注意!

用內建函式log2(n)式不會過的喔!

AtCoder ABC 215 A

題目連結:AtCoder Beginner Contest 215: A – Your First Judge

題目敘述 :

給定一個字串 S, 輸出 AC 若 S=="Hello,World!" 否則輸出 WA.

輸入說明 :

輸⼊一行字串

範例輸入 1 :

Hello,World!

範例輸出 1 :

AC

範例輸入 2 :

Hello,world!

範例輸出 2 :

WA

題解 :

直接判斷即可(s == "Hello,World!")

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    string ipt;
    cin>>ipt;
    if(ipt=="Hello,World!"){
        cout<<"AC";
    }else{
        cout<<"WA";
    }
}