小白月赛103E题(冰冰的GCD) - 优化时间复杂度 有两个很有意思的点

关于查找倍数、公因数 优化时间复杂度 有两个很有意思的点

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define endl '\n'
#define mp make_pair
#define M(x) x%=mod,x+=mod,x%=mod;
#define FOR(i,j,k) for(int i=(j);i<=(k);i++)
#define ROF(i,j,k) for(int i=(j);i>=(k);i--)
#define ANS cout<<ans<<endl;
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
typedef long long ll;
ll n,m,x;
inline void solve()
{
    cin>>n>>m;
    vector<ll> a(n+1),b(n+1),c(n+1),reva(n+1);
    FOR(i,1,n){
        cin>>a[i];
        reva[a[i]]=i;
    }
    FOR(i,1,n){
        cin>>b[i];
    }
    FOR(i,1,n){
        cin>>c[i];
    }
    vector<ll> g(n+1,0),f(n+1,0);
    vector<int> p[n+1];
    FOR(i,2,n){
        for(int j=1;j*i<=n;j++){
            p[j*i].push_back(i);
        }
    }
    vector<ll> jud(n+1,n+1);
    ROF(x,n,1){
        int idx=n+1;
        for(int i:p[b[x]]){
            if(idx>jud[i]){
                           //获取了有同样公因子的后面的数,
                idx=jud[i];//而且获取的是下标最小的数，
                           //符合题意找b[i]下标最小的数
            }
        }
        if(idx==n+1){
            f[x]=b[x];
        }else{
            f[x]=__gcd(b[x],b[idx]);
        }
        for(int i:p[b[x]]){
            jud[i]=x;
        }
    }
    FOR(x,1,n){
        for(int i=1;i*x<=n;i++){
            if(reva[i*x]>=c[x])g[x]++;//直接遍历倍数，而不是遍历所有找倍数
        }
    }
    while(m--){
        cin>>x;
        cout<<g[f[x]]<<endl;
    }
}
int main()
{
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
        solve();
    return 0;
}