计蒜客-2019 蓝桥杯国赛 B 组模拟赛-游戏

思路：想做下计蒜客的模拟赛，结果TM竟然还要收费。。。因此只能在网上找了篇博客做下了：https://www.cnblogs.com/fisherss/p/10857705.html

1.首先 c + d = 2*a + b - a  =  a + b = mod 2.d = b - a = b - (mod - b) = 2*b - mod = 2*b %mod  所以 b-a也就等价于 b*2,等价后a与b交不交换都无所谓(c=2*a,d=2*b,操作都是乘2，只是a取较小值罢了)  3.进行k轮，则ans=a*(2^k)。结果确保A更小,A=min(ans,mod-ans) 答案：383513242709218605

Code：

/* 1.首先 c + d = 2*a + b - a = a + b = mod 2.d = b - a = b - (mod - b) = 2*b - mod = 2*b %mod 所以 b-a也就等价于 b*2,等价后a与b交不交换都无所谓(c=2*a,d=2*b,操作都是乘2，只是a取较小值罢了) 3.进行k轮，则ans=a*(2^k)。结果确保A更小,A=min(ans,mod-ans) 答案：383513242709218605 */ #include<iostream> #include<algorithm> #include<cmath> #include<map> using namespace std; typedef long long LL; typedef pair<int,int> pr; typedef __int128 LLL; const int MAX_N=1e5+5; int n,m,T; LL MOD; LLL a = 482333897982347239LL; LL b = 557432748293424892LL; LL p = 1389472389742429877LL; map<LL,int> imap; LL quick_pow(LL a,LL b); LL quick_mult(LL a,LL b); int main() { ios::sync_with_stdio(false); MOD=a+b; //用快速幂+快速乘 LL ans=quick_pow(2,p); ans=quick_mult(a,ans); ans=min(ans,MOD-ans); cout<<ans<<endl; //利用__int128类型+快速幂 LLL res=a; a=2; while(p){ if(p&1) res=res*a%MOD; a=a*a%MOD; p>>=1; } res=min(res,MOD-res); cout<<(LL)res<<endl; return 0; } LL quick_pow(LL a,LL b) { LL res=1; while(b){ if(b&1) res=quick_mult(res,a); a=quick_mult(a,a); b>>=1; } return res; } LL quick_mult(LL a,LL b) { LL res=0; while(b){ if(b&1) res=(res+a)%MOD; a=a*2%MOD; b>>=1; } return res; }