牛客寒假训练营6 阿宁的倍数

本是古典何须时尚 2024-03-26 14:52 59阅读 0赞

**依旧是慢慢补寒假的题**

[B-阿宁的倍数\_2023牛客寒假算法基础集训营6 (nowcoder.com)][B-_2023_6 _nowcoder.com]

题意：

![2961fe5d6e1a3a42ba6f9edaae8bf27e.png][]

思路：

我们要求的其实是某个位置的后缀map

那么只需要维护前缀map然后差分一下就可以

即，对于一个位置i，去维护1~i的map，map含义是该数作为因子的倍数个数

因此，对于每一个位置i，去枚举其约数，维护一下map

然后答案就是全部的倍数个数减前缀倍数个数

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    int n,m;
    int a[mxn<<1],op[mxn],x[mxn],mp[mxn],u[mxn<<1];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>op[i]>>x[i];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=a[i]/j;j++){
                if(a[i]%j==0){
                    mp[j]++;
                    if(j!=a[i]/j) mp[a[i]/j]++;
                }
            }
            u[i]=mp[a[i]];
        }
        for(int i=1;i<=m;i++){
            if(op[i]==1){
                a[++n]=x[i];
                for(int j=1;j<=a[n]/j;j++){
                    if(a[n]%j==0){
                        mp[j]++;
                        if(j!=a[n]/j) mp[a[n]/j]++;
                    }
                }
                u[n]=mp[a[n]];
            }else{
                cout<<mp[a[x[i]]]-u[x[i]]<<'\n';
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[B-_2023_6 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/46814/B
[2961fe5d6e1a3a42ba6f9edaae8bf27e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7c69564bd009408e8009ab618825a3ec.png