AtCoder Beginner Contest 152 A-E

EdGrass / 2023-05-12 / 原文

AtCoder Beginner Contest 152

A - AC or WA

void solve(){
    int n=read(),m=read();
    puts(n==m?"Yes":"No");
}

B - Comparing Strings

void solve(){
    int n=read(),m=read();
    if(m<n)swap(n,m);
    for(int i=1;i<=m;i++){
        cout<<n;
    }
}

C - Low Elements

int a[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int minn=inf,ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]<minn){
            minn=a[i];
            ans++;
        }
    }
    cout<<ans<<'\n';
}

D - Handstand 2

对每个数取头尾构成dp数组然后穷举（dp真好用）

int dp[20][20];
void solve(){
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        int y=i%10;
        int x=i;
        while(x>=10){
            x/=10;
        }
        dp[x][y]++;
    }
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            ans+=dp[i][j]*dp[j][i];
        }
    }
    cout<<ans<<'\n';
}

E - Flatten

对于巨大的lcm作为分子不能取模需要采用一些方法

本来应该是(lcm/a[1]+lcm/a[2]+···+lcm/a[n]) 用逆元表示为(lcm* inf[1]+lcm* inf[2]+···+lcm* inf[n])

提取公因子后lcm就可以取模了

map<int,int>mp;
int a[N];
int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            mp[i]=max(mp[i],s);
        }
    if (x > 1) mp[x]=max(mp[x],1ll);
}
void solve(){
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        divide(a[i]);
        ans+=qmi(a[i],mod-2,mod);
        ans%mod;
    }
    int j=1;
    for(auto i=mp.begin();i!=mp.end();i++){
        int x=qmi(i->first,i->second,mod);
        ans*=x;
        ans%=mod;
    }
    cout<<ans<<'\n';
}