您当前位置：首页 > php开源 > php教程 > BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树

BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树

来源：程序员人生发布时间：2015-06-30 08:42:34 阅读次数：3521次

题目大意：给定1个序列，屡次询问某段区间乘积的 $varphi$ 值对 $1000777$ 的模

我居然卡过去了233333
将序列分块，记录 $f_{i,j}$ 表示第 $i$ 块左端点到第 $j$ 个点中出现的所有质数 $p$ 的 $frac{p⑴}p$ 之积
每次询问 $[x,y]$ ，首先取出 $[x,y]$ 区间内所有数的积，然后乘上 $f_{st,y}$ （其中 $st$ 是 $x$ 后面第1个块端点所在块）
现在还剩 $[x,l[st]]$ 部份没有统计
由于 $10^6$ 之内的数分解得到的不同的质因数最多只有 $7$ 个，因此暴力枚举零碎部份的质数便可
现在对每一个质数我们需要判断是不是出现过
我们只需要判断这个质数下1次出现的位置是不是大于 $y$ 便可
用10字链表弄1弄就能够了
时间复杂度 $O(7msqrt n)$

这固然不是正解- -
珍重生命，阔别卡常，我们来看正解吧

实际上我们要统计的就是 $[x,y]$ 区间内所有出现过的质数 $p$ 的 $frac{p⑴}p$ 之积
我们想到了甚么？没错，HH的项链！
由于强迫在线，因此我们用可持久化线段树弄1弄就好了。时间复杂度 $O(mlog n)$

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 50500
#define B 700
#define MOD 1000777
using namespace std;
struct abcd{
    abcd *up,*rt;
    int p,belong;
    void* operator new (size_t)
    {
        static abcd mempool[M*7],*C=mempool;
        return C++;
    }
}*head[M],*last[80800];
int n,m,b,last_ans;
int a[M];
int prime[80800],tot;
long long inv[MOD];
int l[M],belong[M];
int prod[B][M];
void Linear_Shaker()
{
    static bool not_prime[1001001];
    int i,j;
    for(i=2;i<=1000000;i++)
    {
        if(!not_prime[i])
            prime[++tot]=i;
        for(j=1;prime[j]*i<=1000000;j++)
        {
            not_prime[prime[j]*i]=true;
            if(i%prime[j]==0)
                break;
        }
    }
    for(inv[1]=1,i=2;i<MOD;i++)
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}
abcd* Decomposition(int pos)
{
    int i,n=a[pos];
    abcd *re=0x0;
    for(i=1;prime[i]*prime[i]<=n;i++)
        if(n%prime[i]==0)
        {
            abcd *temp=new abcd;
            temp->up=re;
            temp->p=i;
            temp->belong=pos;
            if(last[i])
                last[i]->rt=temp;
            re=last[i]=temp;

            while(n%prime[i]==0)
                n/=prime[i];
        }
    if(n!=1)
    {
        i=lower_bound(prime+1,prime+tot+1,n)-prime;

        abcd *temp=new abcd;
        temp->up=re;
        temp->p=i;
        temp->belong=pos;
        if(last[i])
            last[i]->rt=temp;
        re=last[i]=temp;
    }
    return re;
}
int Query(int x,int y)
{
    int i,st=belong[x-1]+1,re=inv[a[x-1]]*a[y]%MOD;
    abcd *temp;
    if(y>=l[st])
        re=(long long)re*prod[st][y]%MOD;
    for(i=min(y,l[st]-1);i>=x;i--)
        for(temp=head[i];temp;temp=temp->up)
            if(!temp->rt||temp->rt->belong>y)
                re=re*inv[prime[temp->p]]%MOD*(prime[temp->p]-1)%MOD;
    return re;
}
namespace IStream{  
    const int L=1<<15;  
    char buffer[L],*S,*T;  
    inline char Get_Char()  
    {  
        if(S==T)  
        {  
            T=(S=buffer)+fread(buffer,1,L,stdin);  
            if(S==T) return EOF;  
        }  
        return *S++;  
    }  
    inline int Get_Int()  
    {  
        char c;  
        int re=0;  
        for(c=Get_Char();c<'0'||c>'9';c=Get_Char());  
        while(c>='0'&&c<='9')  
            re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();  
        return re;  
    }  
}
int main()
{
    using namespace IStream;
    int i,j,x,y;
    abcd *temp;
    cin>>n>>m;
    b=200;
    Linear_Shaker();
    for(i=1;i<=n;i++)
    {
        a[i]=Get_Int();
        head[i]=Decomposition(i);
    }
    for(a[0]=1,i=1;i<=n;i++)
        a[i]=(long long)a[i]*a[i-1]%MOD;
    for(i=1;i<=n;i++)
        belong[i]=(i-1)/b+1;
    for(i=1;i<=belong[n];i++)
        l[i]=(i-1)*b+1;
    l[i]=0x3f3f3f3f;

    static int v[80800],ans;
    for(j=1;j<=belong[n];j++)
    {
        ans=1;
        for(i=l[j];i<=n;i++)
        {
            for(temp=head[i];temp;temp=temp->up)
                if(v[temp->p]!=j)
                {
                    v[temp->p]=j;
                    ans = ans * inv[prime[temp->p]] % MOD * (prime[temp->p]-1) % MOD ;
                }
            prod[j][i]=ans;
        }
    }

    for(i=1;i<=m;i++)
    {
        x=Get_Int();
        y=Get_Int();
        x^=last_ans;
        y^=last_ans;
        printf("%d
",last_ans=Query(x,y));
    }
    //puts("Fuck♂You!");
    return 0;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 使用oledb对数据库进行增删改查及批量插入操作

下一篇 UML（统一建模语言）概述

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点