排列询问

[编程题]排列询问

热度指数：996 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹有一个长度为n的排列p，她有q个询问。

每个询问包含 $l1$ ， $r1$ ， $l2$ ， $r2$ .她想知道从 $[l1,r1]$ 中选取 $x$ ， $[l2,r2]$ 中选取 $y$ ,有多少组 $(x,y)$ 满足 $min(x,y)==gcd(x,y)?$

返回一个vector代表对这q个询问的答案

示例1

输入

6,1,[1,2,3,4,5,6],[0],[1],[2],[3]

输出

[3]

说明

(1,3),(1,4),(2,4)三对

备注:

n，q，p数组，l1数组，r1数组，l2数组，r2数组 

 <

算法知识视频讲解

阿米诺斯

function PermutationQuery( n ,  q ,  p ,  l1 ,  r1 ,  l2 ,  r2 ) {
    let counter=[];
    for(let i=0;i<q;i++){
        counter[i]=0;
       for(let l=l1[i],r=r1[i],a=l;a<=r;a++){
           for(let z=l2[i],x=r2[i],c=z;c<=x;c++){
               if(Math.min(p[a],p[c])==gcd(p[a],p[c])){
                   counter[i]++;
               }
           }
       }
    }
    return counter;
}

发表于 2021-03-14 00:42:11 回复(0)