首页 » 莫队算法 » 正文

名哥的完全平方数


来源:https://www.nowcoder.com/acm/contest/127/J

511 CF第一人名哥不上紫名不实习!
这天,名哥上CF刷了一道有趣的题(CF 480D),意犹未尽!
跟数学大佬浩佬吹嘘,浩佬看了题目:”这太简单了!我改一下,看你能做出来吗? 给一个长度为n的数组,做q次询问,每次询问区间[l,r]里有多少对数的乘积为完全平方数?”
名哥呆了,您能帮名哥解决吗?

输入描述:

第一行输入 n(1≤n≤3*10^5) ,表示数组的长度。
第二行输入a1……an(-1000000≤ai≤1000000)
第三行输入q(1≤n≤3*10^5) , 表示询问的次数
下面q行,每行两个整数表示查询的区间:l,r(1≤l≤r≤n)

输出描述:

对每次查询输出一行:输出1个整数 ans ,表示查询区间的两个数的乘积为完全平方数的对数。

示例1

输入

复制

5
1 -4 -36 2 0
4
1 2
2 3
3 5
4 4

输出

复制

0
1
2
0

思路

对于两个数相乘为完全平方数的两个数,有两种情况:

  1. 其中一个数为0;

  2. 两个数将他们的完全平方数的因子除掉,得到的数相同,分正数负数;

因为中间的操作并没有修改,所以选择莫队算法。用打表将除去完全平方数的因子存起来。

详见代码…

代码

使用的 https://www.nowcoder.com/acm/contest/view-submission?submissionId=27632677 侵权可联系删除

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6+88;
int l,r,zero,pos[N],A[N],P[N],P2[N], cnt1[N],cnt2[N],ans[N],Ans;
struct node{
    int l,r,id;
    bool operator < (const node &A){  //首先比较快的大小,相同比较右边节点的大小
        return pos[l]==pos[A.l]?r<A.r:pos[l]<pos[A.l];
    }
}Q[N];
void init(){  //将每个数去掉平方因数之后的数
    for(int i=1;i<=1000000;++i) P[i]=i;  //赋值
    for(int i=2;i<=1000000;++i) {  //化简
        if(P[i]==i) {  //该数没有平方因数
            for(int j=i<<1;j<=1000000;j+=i) {
                while(P[j]%(i*i)==0) P[j]/=i*i;
            }
        }
    }
}
int calc(int x){  //C(x,2),x个数中取两个
    return x*(x-1)/2;
}
void work(int x,int f){
    if(A[x]==0) zero+=f;
    else if(A[x]>0) {
        Ans-=calc(cnt1[P[A[x]]]);  //先减去原来的 
        cnt1[P[A[x]]]+=f;
        Ans+=calc(cnt1[P[A[x]]]);  //再加上现在的 
    }
    else {
        Ans-=calc(cnt2[P2[-A[x]]]);  //不知道为啥可以不加- 
        cnt2[P2[-A[x]]]+=f;
        Ans+=calc(cnt2[P2[-A[x]]]);
    }
}
int main(){
    int m,n,block;
    init();  //初始化打表
    scanf("%d",&n);  //输入数组长度
    block=(int)sqrt(n);  //分块的大小
    for(int i=1;i<=1000000;++i) pos[i]=i/block;  //分块
    for(int i=1;i<=n;++i) scanf("%d",A+i);  //输入每个位置数的值
    scanf("%d",&m);  ///输入次数
    for(int i=1;i<=m;++i) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;  //id记录第几次的结果
    sort(Q+1,Q+m+1);  //排序
    l=1,r=0;  //开始区间没一个数
    for(int i=1;i<=m;++i) {  //对于一次次的查询,进行一个个的加入
        while(l<Q[i].l) work(l,-1),++l;
        while(l>Q[i].l) --l,work(l,1);
        while(r>Q[i].r) work(r,-1),--r;
        while(r<Q[i].r) ++r,work(r,1);
        ans[Q[i].id]=Ans+zero*(r-l)-calc(zero);  //对 0 只是单独的计算个数,最后需要加上 
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
}
赞 (0)

发表评论