快速幂问题+中国剩余定理

2019-04-14 18:58发布

站内文章 / 模拟电子
17151 0 1619
poj 3233 矩阵快速幂+二分求解 题目传送门 //矩阵快速幂+二分 #include #include #include using namespace std; const int maxn=30+5; typedef struct{ int mar[maxn][maxn]; }MATRAX; MATRAX a,per; //初始矩阵 单位矩阵 int n,m; void init() { memset(per.mar,0,sizeof(per.mar)); for(int i=0;i>=1; } return ans; } MATRAX MatraxSum(int k) { if(k==1) return a; MATRAX temp,b; temp=MatraxSum(k/2); if(k&1) { b=pow_mod(k/2); temp=add(temp,multi(temp,b)); temp=add(temp,pow_mod(k)); } else { b=pow_mod(k/2); temp=add(temp,multi(temp,b)); } return temp; } int main() { int k; while(scanf("%d%d%d",&n,&k,&m)==3) { init(); MATRAX solve; solve=MatraxSum(k); for(int i=0;i poj 1995 快速幂 题目传送门 //矩阵快速幂 #include #include using namespace std; typedef long long LL; LL pow_mod(LL a,LL b,LL MOD) { LL res=1; while(b) { if(b&1) res=res*a%MOD; a=a*a%MOD; b>>=1; } return res; } int main() { int T; scanf("%d",&T); while(T--) { LL M,ans=0; scanf("%lld",&M); int k; scanf("%d",&k); for(int i=0;i poj 1006 中国剩余定理      特殊的有规律的线性同余方程组 题目传送门 //中国剩余定理 #include #include using namespace std; typedef long long LL; void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y) { if(b==0) { d=a; x=1; y=0; return; } else { ex_gcd(b,a%b,d,x,y); LL temp=x; x=y; y=temp-(a/b)*y; } } int main() { int kase=0; LL p,e,i,d; while(scanf("%lld%lld%lld%lld",&p,&e,&i,&d)==4) { if(p==-1&&e==-1&&i==-1&&d==-1) break; LL ans=0,f,x,y,M=23*28*33; ex_gcd(28*33,23,f,x,y); ans=(ans+28*33*x*p)%M; ex_gcd(23*33,28,f,x,y); ans=(ans+23*33*x*e)%M; ex_gcd(23*28,33,f,x,y); ans=(ans+23*28*x*i)%M; ans=ans-d; if(ans<=0) ans+=M; printf("Case %d: the next triple peak occurs in %lld days. ",++kase,ans); } return 0; } hdu 1788 两种解法 题目传送门 1.找到了一定的规律，发现只需要求出这些数的最小公倍数，再减a即可 //中国剩余定理 #include #include using namespace std; typedef long long LL; LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } int main() { LL n,a; while(scanf("%lld%lld",&n,&a)==2) { if(n==0&&a==0) break; LL M=1; for(int i=0;i 2.求解线性同余方程组 //求解线性同余方程组 #include #include using namespace std; typedef long long LL; void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y) { if(b==0) { d=a; x=1; y=0; return; } else { ex_gcd(b,a%b,d,x,y); LL temp=x; x=y; y=temp-(a/b)*y; } } int main() { LL n,a; while(scanf("%lld%lld",&n,&a)==2) { if(n==0&&a==0) break; LL r,k; scanf("%lld",&k); r=k-a; for(int i=0;i  

热门文章