cf1154G 埃氏筛应用

直接用埃氏筛也可以做，但是这题写起来有点恶臭。。

更加简单的写法是直接枚举gcd=k，然后里面再枚举一次i*k，即找到k两个最小的倍数，看起来复杂度很高，但其实也是埃氏筛的复杂度

因为每次枚举gcd，相当于筛法中的枚举筛数，不同的是这题对于每个i在筛的过程中，不会筛到低，而是会中途退出循环，那么当其倍数i*k继续去筛的时候，仅仅是原来应该筛的数筛掉而已

int value[][];

int main() {

    int n;

    scanf("%d",&n);

    memset(value,,sizeof(value));

    for(int i = ;i<=n;i++){

        int x;

        scanf("%d",&x);

        if(value[x][]){

            value[x][]=i;

        }

        else{

            value[x][]=i;

        }

    }

    LL ans=1e18,ansx,ansy;

    for(int i = ;i<=1e7;i++){

        vector<pll> v;

        for(int k=;k*i<=1e7;k++){

            if(value[k*i][]){

                v.pb(mp(k,value[k*i][]));

            }

            if(value[k*i][]){

                v.pb(mp(k,value[k*i][]));

            }

            if(v.size()>=)

            break;

        }

        if(v.size()<)

        continue;

        LL lcm=i*v[].x*v[].x;

        if(lcm<ans){

            ans=lcm;

            ansx=v[].y;

            ansy=v[].y;

        }

    }

    if(ansx>ansy)

    swap(ansx,ansy);

    printf("%lld %lld\n",ansx,ansy);

}

巴特西

cf1154G 埃氏筛应用

最新文章

热门文章