51Nod 1417 天堂里的游戏

Problem

正当Noder惊魂未定的时候，走来一个美女，要求和他一起玩个数学游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你A元，如果我们都是反面，我给你B元（A + B为偶数）。剩下的情况你给我（A + B） / 2元就可以了。

Noder知道这个游戏他多半要输，可他并不在乎，他只想让自己输的慢一点。

那么你来帮美女计算一下，她选择出正面的概率应该是多少（以最简分数形式输出）？

Solution

混合策略纳什平衡，详见纳什平衡-百度百科

设你出正面和反面概率是x,(1-x)，美女出正面和反面概率是y,(1-y)。列表，写出美女出正面，你的期望收益，美女出反面，你的期望收益，让两者相等，否则美女可以通过改变她的概率来使你的期望收益降低。

美女	正面	反面
正面	A	-(A+B)/2
反面	-(A+B)/2	B

A * x - (A+B)/2 * (1-x) = -(A+B)/2 * x + B * ( 1-x )

解出x = (a+3b) / 4(a+b)

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#define mod 998244353LL
#define mem(ss) memset(ss,0,sizeof(ss))
#define ll long long
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;}
ll lowspeed(ll a,ll b,ll p){ll cur=a,ans=0;while(b){if(b&1) ans=(ans+cur)%p;cur=(cur+cur)%p;b>>=1;}return ans%p;}
ll speed(ll a,ll b,ll p){ll cur=a,ans=1;while(b){if(b&1) ans=lowspeed(ans,cur,p)%p;cur=lowspeed(cur,cur,p)%p;b>>=1;}return ans%p;}
ll T,A,B;
int main(){
    io_opt;
    cin>>T;
    while(T--){
        cin>>A>>B;
        ll x=A+3*B;
        ll y=4*(A+B);
        ll gd=gcd(x,y);
        cout<<x/gd<<'/'<<y/gd<<endl;
    }
    return 0;
}