【CodeForces】906 D. Power Tower 扩展欧拉定理-白红宇

【CodeForces】906 D. Power Tower 扩展欧拉定理

阅读量：6095 次

发布时间：2019-06-20

本文共 2061 字，大约阅读时间需要 6 分钟。

【题目】

【题意】给定长度为n的正整数序列和模数m，q次询问区间[l,r]累乘幂%m的答案。n,q<=10^5，m,ai<=10^9。

【算法】扩展欧拉定理

【题解】扩展欧拉定理的形式：

$$a^b\equiv a^{b\%\varphi(p)+\varphi(p)} \ \ mod \ \ p \ \ (b\geq \varphi(p))$$

特别注意当b<φ(p)且(a,p)≠1时不变。

假如现在是三个累乘幂a^(b^c)，那么根据扩展欧拉定理：

$$a^{b^c}\ \ mod \ \ p\equiv a^{b^c\%\varphi(p)+\varphi(p)} \ \ mod \ \ p$$

这样我们只需要计算：

$$b^c\ \ mod \ \ \varphi(p)$$

更多个累乘幂的时候只需要不断递归取φ，直至1为止（φ(1)=1）。可以证明至多log(p)次可以得到答案。

这样计算累乘幂的复杂度就是O(log p*log n)，也即一次询问的极限复杂度。

这里过程中用到的欧拉函数至多log p个，直接暴力求解，预处理复杂度O(log p*√n)，用map存储，实现中可以直接记忆化。

总复杂度O(q*log p*log n)。

#include
      
       #include
       #define ll long longbool isdigit(char c){
    return c>='0'&&c<='9';}int read(){    int s=0,t=1;char c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}using namespace std;const int maxn=100010;map
        
         p;int a[maxn],n,m,q;int phi(int n){    if(p.count(n))return p[n];    int ans=n,m=n;    for(int i=2;i*i<=n;i++)if(n!=1&&n%i==0){        ans=ans/i*(i-1);        while(n%i==0)n/=i;    }    if(n>1)ans=ans/n*(n-1);    p[m]=ans;    return ans;}int mod(ll x,int y){
    return x
         
          intint power(int x,int k,int m){    int ans=1;    while(k){        if(k&1)ans=mod(1ll*ans*x,m);        x=mod(1ll*x*x,m);        k>>=1;    }    return ans;}int calc(int l,int r,int m){    if(l==r||m==1)return mod(a[l],m);    return power(a[l],calc(l+1,r,phi(m)),m);}    int main(){    n=read();m=read();    for(int i=1;i<=n;i++)a[i]=read();    q=read();    while(q--){        int l=read(),r=read();        printf("%d\n",calc(l,r,m)%m);    }    return 0;}

View Code

实现：

1.递归过程中直接返回ans+mod，这样下一层就自带+φ(m)了，最后输出答案记得%m就可以了。

2.快速幂过程中的取模改为 int mod(ll x,int y){return x<y?x:x%y+y;} ，这样到某一次数字超过y之后，后面每次都会强制超过y然后+y直至最后一次。

【BZOJ】4869 相逢是问候

因为至多log次，所以暴力计算维护线段树，n个数字，每个至多log p次修改，每次都要重新计算一次log p，快速幂log n。所以复杂度O(n log3n)。

预处理phi的递归序列，然后转化为非递归计算常数比较小。

代码见：

有一种优化方法，因为快速幂至多1e8且都是以c为底，可以预处理c^(0~1e4)，令t=c^(1e4)，再预处理t^(0~1e4)，这样对于一个数字查一下大表t再定位到小表c就行了。

这就是传说中的分段打表，具体见：

转载于:https://www.cnblogs.com/onioncyc/p/8933040.html

你可能感兴趣的文章