C20220712T1 牛半仙的妹子数

给定 \(A,B,C\) ，操作 \(K\) 次，每次操作若 \(A+B\leq C\) 则 \(A=2A,B=2B,C=C-A-B\) ，否则记 \(A,B\) 中较小的为 \(W\) ， \(P=min(\frac{C}{2},W-1)\) ，则 \(A=A-P,B=B+P-C,C=2C\) ，求操作后的 \(C\) 。\(sum\leq 10^9,k\leq 10^9\) 。

先给出结论，答案为 \(C=(C\times 2^k)\,\,mod\,\,(A+B+C)\) 。首先可以把 \(A,B\) 看成整体，那么操作就变成了要么 \(C=2C\) ，要么 \(C=C-(sum-C)=2C-sum\) ，而 \(2C-sum\) 在模 \(sum\) 的意义下就是 \(2C\) ,故是正确的。用快速幂解决。

ll mul(ll a,ll b,ll p){
	ll ret=1;
	while(b){
		if(b&1)
			ret=(((ret)%p)*a)%p;
		a=a*a%p;
		b=b>>1;
	}
	return ret;
}
ll t,a,b,c,k,cnt;
int main(){
	t=in();
	while(t--){
		a=in(),b=in(),c=in(),k=in();
		out(c*mul(2,k,a+b+c)%(a+b+c));
		puts("");
	}
	return 0;
}