Menu
April 28, 2015

BZOJ 4026: dC Loves Number Theory


可以先看看wzf的题解学习一下如何做人


Solution

跟数论关系不大,只是用到了公式:

m易求,那么质因子的贡献就是
就是统计一段区间中的元素去重之后的总贡献。

  • 经典问题,建立主席树
  • 每个质因数找到上次出现的位置,将贡献加在上。
  • 询问只要查询的第个元素就可以了。
  • 为什么是对的?
  • 自己yy一下。

代码:

4026.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
inline void readi(int &x);
const int maxn=50005,M=1000777;

int n,Q;
int a[maxn],pm[maxn],fc[maxn][10],fn[maxn];
bool isp[1005];
int pr[1000],pn,inv[M+4];

int las[M];

struct node
{
    int f;
    node *lc,*rc;
}null[10000000],*pns=null+1,*root[maxn];

void Insert(node* &x,int l,int r,const int &a,const int &b,const int &c)
{
    *pns=*x;x=pns++;
    if(l>=a&&r<=b)
        x->f=(LL)x->f*c%M;
    else
    {
        int mid=l+r>>1;
        if(a<=mid)Insert(x->lc,l,mid,a,b,c);
        if(b>mid)Insert(x->rc,mid+1,r,a,b,c);
    }
}

int Query(node* &x,int l,int r,const int &p)
{
    if(l==r)return x->f;
    int mid=l+r>>1;
    return (LL)x->f*(p<=mid?Query(x->lc,l,mid,p):Query(x->rc,mid+1,r,p))%M;
}

void init()
{
    for(int i=2;i<=1000;i++)
    {
        if(!isp[i])pr[++pn]=i;
        for(int j=1;j<=pn&&i*pr[j]<=1000;j++)
        {
            isp[i*pr[j]]=1;
            if(i%pr[j]==0)break;
        }
    }
    inv[1]=1;
  for(int i=2;i<M;i++)
  {
        inv[i]=M-(LL)(M/i)*inv[M%i]%M;
        if(inv[i]==M)inv[i]=0;
    }
    readi(n),readi(Q);
    pm[0]=1;
    for(int i=1,t;i<=n;i++)
    {
        readi(a[i]);
        pm[i]=(LL)pm[i-1]*a[i]%M;
        t=a[i];
        for(int j=1;j<=pn&&pr[j]*pr[j]<=t;j++)
            if(t%pr[j]==0)
            {
                fc[i][fn[i]++]=pr[j];
                while(t%pr[j]==0)t/=pr[j];
            }
        if(t>1)fc[i][fn[i]++]=t;
    }
    null->lc=null->rc=null,null->f=1;
    root[0]=null;
}

void work()
{
    for(int i=1,j,t,pre;i<=n;i++)
    {
        root[i]=root[i-1];
        for(j=0;j<fn[i];j++)
        {
            t=fc[i][j];
            pre=las[t];
            las[t]=i;
            Insert(root[i],1,n,pre+1,i,M+1-inv[t]);
        }
    }
}

void solve()
{
    int ans=0;
    for(int qi=1,l,r;qi<=Q;qi++)
    {
        readi(l),readi(r);
        l^=ans,r^=ans;
        ans=(LL)pm[r]*inv[pm[l-1]]%M*Query(root[r],1,n,l)%M;
        printf("%d\n",ans);
    }
}

int main()
{
    init();
    work();
    solve();
    return 0;
}

inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}

 
comments powered by Disqus