欧拉降幂加快速幂

川长思鸟来 2022-04-24 08:12 159阅读 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 条评论，159人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关牛课暑假多校第四场 A-Ternary String（欧拉降幂）

[传送门][Link 1] 思路：从前往后遍历字符串，如果遇到0，那么时间就是T+1（假设T是之前所用的时间）如果遇到‘1’，时间是2\T+2，因为在之前的T时间，这个

淩亂°似流年/ 2022年05月18日 02:40/ 0 赞/ 127 阅读

相关欧拉降幂加快速幂

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

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

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

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

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

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

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

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

相关欧拉路，欧拉回路

[欧拉路，欧拉回路][Link 1] 转载于:https://www.cnblogs.com/Al-Ca/p/11206978.html [Link 1]: https:

偏执的太偏执、/ 2021年10月26日 11:44/ 0 赞/ 387 阅读

相关欧拉回路欧拉通路欧拉回路图

[来源][Link 1] 一、定义对于无向图：　　1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；　　2) 如果欧拉通路是回路（

灰太狼/ 2021年06月24日 15:57/ 0 赞/ 574 阅读