欧拉降幂加快速幂

川长思鸟来 2022-04-24 08:12 173阅读 0赞

题：[https://ac.nowcoder.com/acm/contest/634/D][https_ac.nowcoder.com_acm_contest_634_D]

求4的n次方减一

借个大佬的图

![70][]

#include<iostream>
    #define ll long long
    using namespace std;
    ll er(ll n){//前n个数中与n互质的个数 
    	ll ans=n;
    	ll i;
    	for(i=2;i*i<=n;i++){
    		if(n%i==0){
    			ans-=ans/i;
    			while(n%i==0) n/=i;
    		}
    	}
    	if(n>1) ans-=ans/n;
    	return ans;
    }
    ll qpow(ll a,ll b,ll c){//快速幂 
    	ll ans=1;
    	while(b){
    		if(b&1){
    			ans=(ans*a)%c;
    		}
    		a=a%c*a%c;
    		b>>=1;
    	}
    	return ans;
    }
    int main(){
    	int T;
    	cin>>T;
    	while(T--){
    		string a;
    		ll mod;
    		cin>>a>>mod;
    		ll k=mod;
    		k=er(mod);
    		ll n=0;
    		for(int i=0;i<a.size();i++){
    			n=n*10+a[i]-'0';
    			n%=k;
    		}
    		
    		ll ant=(qpow(4,n+k,mod)-1+mod)%mod;
    		cout<<ant<<endl;
    	}
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_634_D]: https://ac.nowcoder.com/acm/contest/634/D
[70]: /images/20220217/c48ede2c339942e3ba15f4c2d411d7b2.png

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 FZU-1759——(欧拉降幂，模板题)

题目链接][Link 1] 思路：因为指数非常大，用long long 都存不下，所以要用数组存，然后在通过欧拉降幂取模是指数变小，在通过快速幂求结果注...

港控/mmm°/ 2024年04月18日 09:28/ 0 赞/ 80 阅读

相关数论12——欧拉——欧拉降幂

拉降幂，广义欧拉降幂 ab = ① ab ，b< p ②ab%∮( p )+∮( p ), b >= p 代码（改代码用于解...

╰半夏微凉°/ 2024年04月18日 08:08/ 0 赞/ 87 阅读

相关 E - Exponial Gym - 101550E——(欧拉降幂)

b = ① ab ，b< p ②ab%∮( p )+∮( p ), b >= p [题目链接][Link 1] 本题利用知识点：...

不念不忘少年蓝@/ 2024年04月18日 08:06/ 0 赞/ 75 阅读

相关欧拉降幂，基本计算定理——cf615D

用基本算数定理求约数和的思想来计算，首先用pi,ci来表示第i个质数，指数为i，然后对于每个pi,pi^2...都有指数为mul\{(c\_1+1)(c\_2+1)(c\

男娘i/ 2023年10月12日 08:22/ 0 赞/ 23 阅读

相关 Hdu 3221 Brute-force Algorithm (矩阵欧拉定理降幂)

利用迭代思想，最后推得的规律和Hdu4549一样，我的Hdu4549题解：http://blog.csdn.net/whyorwhnt/article/details/1285

Bertha 。/ 2022年09月17日 12:19/ 0 赞/ 150 阅读

相关 hdu-4549(矩阵快速幂+欧拉定理)

问题描述: M斐波那契数列F\[n\]是一种整数数列，它的定义如下： F\[0\] = a F\[1\] = b F\[n\] = F\[n-1\]

客官°小女子只卖身不卖艺/ 2022年06月09日 04:59/ 0 赞/ 176 阅读

相关【费马小定理降幂+矩阵快速幂+快速幂】M斐波那契数列 HDU - 4549

Think: 1知识点：费马小定理降幂+矩阵快速幂+快速幂（１）：费马小定理降幂：定理：若gcd(A, M) == 1，则A^x = A^(x%Eular(M)

桃扇骨/ 2022年06月07日 11:26/ 0 赞/ 180 阅读

相关欧拉降幂加快速幂

题：[https://ac.nowcoder.com/acm/contest/634/D][https_ac.nowcoder.com_acm_contest_634_D]

川长思鸟来/ 2022年04月24日 08:12/ 0 赞/ 174 阅读

相关吉首大学校赛 A SARS病毒（欧拉降幂）

链接：[https://ac.nowcoder.com/acm/contest/925/A][https_ac.nowcoder.com_acm_contest_925_A]

青旅半醒/ 2021年12月11日 01:03/ 0 赞/ 237 阅读

相关欧拉函数|(扩展)欧拉定理|欧拉反演

[也许更好的阅读体验][Link 1] 欧拉函数欧拉函数是小于 n的数中与n 互质的数的数目符号\\(\\varphi(x)\\)

忘是亡心i/ 2021年11月09日 20:06/ 0 赞/ 448 阅读