牛客練習賽22 E 簡單資料結構1(拓展歐拉定理+樹狀數組)

題目

解析:

首先了解歐拉定理1     歐拉定理2

再是歐拉線性篩

線性篩

最後是拓展歐拉定理

還有小的知識是樹狀數組的區間更新+單點查詢 連結

上官方題解

先線性篩phi

然後考慮用拓展歐拉定理降幂

(這裡a的指數部分應該是

)

我們發現對一個數取歐拉函數，log次就會變成1，而任何數模1肯定=0，是以就可以算出來了。

然而這麼做還會有一些小問題。

首先我們發現後面的phi[p]這一項是可能不會加的

這個怎麼辦呢？

因為這個不斷地幂次增長速度極快，很少幾項就能夠增長到遠大于模數的地步

那就先暴力的處理前面幾項，然後再正常做，這樣就減少了讨論次數

然後加點特判即可

總複雜度O( p + mlognlog*(v) )

這裡需要注意的地方有兩點

1.

上面的x必須是完整的值。例如題目中a[l]^(a[l+1]^(a[l+2]^(a[l+3]^(......a[r])中計算a[l+1]是否需要加上

時，是依據(a[l+1]^(a[l+2]^(a[l+3]^(......a[r])>

?來決定的，不是a[l+1]>

?來決定的

2.在dfs傳回指數k時，計算a[i]^k必須要先讓a[i]%p..........這個具體的我也不知道為什麼,反正沒有就隻能過60%的樣例

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 2e7+10;
const int MAX = 5e5+100;
int prime[MAXN],mark[MAXN];
int tot,phi[MAXN];
ll btree[MAX];

int n;
ll a[MAX];
void getphi(int N)
{
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++)
    {
        if(!mark[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot;j++)
        {
            if(i*prime[j]>N) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                //phi[i*prime[j]]=phi[i]*phi[prime[j]];
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

inline int lowbit(int x)
{
    return x&(-x);
}

void add(int l,ll x)  //區間更新
{
    for(int i=l;i<=n;i+=lowbit(i))
    {
        btree[i]+=x;
    }
}

ll query(int l)   //單點查詢
{
    ll sum=0;
    for(int i=l;i>0;i-=lowbit(i))
        sum+=btree[i];
    return sum;
}


ll quick(ll a,ll b,ll p,int& ok)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            if(ans*a>=p) ok=1;
            ans=ans*a%p;

        }
        if(a*a>=p) ok=1;
        a=a*a%p;
        b=b>>1;
    }
    return ans;
}

ll  dfs(int now,int r,ll p)
{
    ll tmp=query(now);
    if(now==r||p==1)
    {
        //if(cnt!=0)
            return tmp%p+(tmp>=p?p:0);
        /*else
            return tmp%p;*/
    }
    /*if(p==1)
    {
        //ll tmp=query(now);
        //if(cnt!=0)
            return 1;
        //else
            //return 0;
    }*/
    ll k=dfs(now+1,r,(ll)phi[p]);
    int ok=0;
    if(tmp>=p) ok=1,tmp=tmp%p;   //！！！tmp=tmp%p
    ll ans= quick(tmp,k,p,ok);
    if(ok)
    {
        ans+=p;
    }
    //if(cnt!=0)
        return ans;
    //else
    //    return ans%p;

}

int main()
{
    getphi(MAXN-2);
    int m;
    scanf("%d%d",&n,&m);
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        //add(i,a[i]);
        //add(i+1,-a[i]);
        add(i,a[i]-a[i-1]);
    }
    for(int i=0;i<m;i++)
    {
        int l,r,mode;
        ll x;
        scanf("%d%d%d%lld",&mode,&l,&r,&x);
        if(mode==1)
        {
            add(l,x);
            add(r+1,-x);
        }
        else
        {
            printf("%lld\n",dfs(l,r,x)%x);  //%x用于去除dfs内a[l]%x時加上x的情況
        }
    }
    return 0;
}