Luogu P5091 欧拉定理&&CF17D Notepad

P5091

题意

链接
求\(a^b \bmod p\),\(b \le 10^{20000000}\)

Idea

这是个模板题，
使用扩展欧拉定理
\[a^b =\begin{cases} a^b,b<phi(p)\\a^{b \bmod phi(p) + phi(p)},b \ge phi(p) \end{cases}\]
上面的操作又称欧拉降幂

证明

Code

int phi[maxn],prime[maxn],f[maxn];
char s[20000010];
inline int power(int a,int b,int p){
    int ans=1%p;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}
inline void init(int x){
    int t=0;
    phi[1]=1;
    for(int i=1;i<=x;i++){
        if(!phi[i]) phi[i]=i-1,prime[++t]=i;
        for(int j=1;j<=t&&i*prime[j]<=x;j++){
            if(!(i%prime[j])){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}
signed main(){
    int n=read(),p=read();
    init(p);
    scanf("%s",s+1);
    int len=strlen(s+1),d=0;
    int tmp=0; bool book=1;
    for(int i=1;i<=len;i++){
        d=(d*10+(s[i]-48))%phi[p];
        tmp=(tmp*10+(s[i]-48));
        if(tmp>phi[p]) book=0;
    }
    int ans=power(n,book?tmp:d+phi[p],p);
    printf("%d",ans);
    return 0;
}

CF17D Notepad

题意

Luogu的
CF的
有个本子，往本子上写全部长度为\(n\)的\(b\)进制数,每页可以写\(c\)个。
要求数字要求所有数字必须严格不含前导0。求最后一页上有多少个数字。

Idea

考虑第一位不能为0，只能有\(b-1([1,b-1])\)种填法
考虑后\(n-1\)位可以填\([0,b-1]\)，则有\(b^{n-1}\)种填法
则显然\(ans=(b-1)\times b^{n-1} \bmod c\)
若\(ans=0\) ，则答案为\(p\)，因为不用翻开下一页
如何求\(ans\)呢？
欧拉降幂即可。

Code

inline int power(int a,int b,int p){
    int ans=1%p;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}
inline int phi(int x){
    int t=x,tot=x;
    for(int i=2;i*i<=t;i++)
    if(!(x%i)){
        tot=tot/i*(i-1);
        while(!(x%i)) x/=i;
    }
    return x>1?tot/x*(x-1):tot;
}
char s1[maxn],s2[maxn];
int b[maxn],p;
signed main(){
    scanf("%s %s %d",s1+1,s2+1,&p);
    int len1=strlen(s1+1),len2=strlen(s2+1);
    int d1=0,d2=0,Phi=phi(p);
    for(int i=1;i<=len1;i++) d1=(d1*10+(s1[i]-48))%p;
    for(int i=1;i<=len2;i++) b[i]=s2[i]-48;
    b[len2]--;
    for(int i=len2;i;i--)
    if(b[i]<0) b[i]+=10,b[i-1]--;
    else break;
    int tmp=0; bool book=1;
    for(int i=1;i<=len2;i++){
        d2=(d2*10+b[i])%Phi;
        tmp=tmp*10+b[i];
        if(tmp>=Phi) book=0;
    }
    int ans=(d1+p-1)%p*power(d1,book?tmp:d2+Phi,p)%p;
    printf("%d",!ans?p:ans);
    return 0;
}

\(\text{浮生若梦,为欢几何,不如许一个安然无忧}\)