51nod1185威佐夫博弈+大数乘法模拟
题目就是正常的威佐夫博弈 关于威佐夫博弈三大博弈详解
但是范围是1e18 因为威佐夫博弈需要乘以黄金分割数1.618....... 所以在乘的时候会损失精度
需要模拟下大数乘法 关于大数乘法模拟大数乘法原理及实现
这里再简单说一下 如何模拟的乘法 模拟小学生竖式运算
举个例子 三位数 123 乘以两位数 45
百位 | 十位 | 各位 | ||
1 | 2 | 3 | ||
乘 | 4 | 5 | ||
—————————————————————————————————— | ||||
6(5+1) | 1(10+1进1) | 5(15进1) | ||
4 | 9(8+1) | 2(进1) | ||
ans | 5 | 5 | 3 | 5 |
这个大家都会 等于 5535
那么 抽象一下
a0 a1 a2 三位数
t2 t1 两位数
---------------------------------------------------
t1*a0 t1*a1 t1*a2
t2*a0 t2*a1 t2*a2
——————————————————进位累加得到答案
那么我们也是这样模拟 将1.618先不管1 只看后边的小数
ll a[3]={618033988,749894848,204586834};//分成三部分 每部分是1e9
然后把 k 分成两部分
ll t1=k%mod;//后半部分
ll t2=k/mod;//前半部分 都是1e9大小
然后按照刚才列的竖式进行计算 注意进位 就ok了
ll ans=t1*a[2]; //可以看作三位数乘两位数得到的结果的个位
ans=t1*a[1]+t2*a[2]+ans/mod;//十位
ans=t1*a[0]+t2*a[1]+ans/mod;//百位
ans=t2*a[0]+ans/mod; //千位
ans+=k;//注意刚开始 忽略了1.618的1 现在要加上k 也就是算上那个1
ac代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e4+7;
typedef long long ll;
//0.6180339887 4989484820 4586834365
ll a[3]={618033988,749894848,204586834};
ll mod=1e9;
int T;
ll A,B;
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&A,&B);
ll x=min(A,B);
ll y=max(A,B);
ll k=y-x;
// k*黄金比例
ll t1=k%mod;
ll t2=k/mod;
ll ans=t1*a[2];
ans=t1*a[1]+t2*a[2]+ans/mod;
ans=t1*a[0]+t2*a[1]+ans/mod;
ans=t2*a[0]+ans/mod;
ans+=k;
if(ans==x) printf("B\n");
else printf("A\n");
}
return 0;
}