您當前位置：首頁 > php開源 > php教程 > BZOJ 4026 dC Loves Number Theory 分塊+十字鏈表/可持久化線段樹

BZOJ 4026 dC Loves Number Theory 分塊+十字鏈表/可持久化線段樹

來源：程序員人生發布時間：2015-06-30 08:42:34 閱讀次數：3671次

題目大意：給定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關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

BZOJ 4026 dC Loves Number Theory 分塊+十字鏈表/可持久化線段樹