当前位置: 代码迷 >> 综合 >> FZU2294 Uint47 calculator(快速乘取模)
  详细解决方案

FZU2294 Uint47 calculator(快速乘取模)

热度:61   发布时间:2023-11-22 00:28:58.0

解题

用map来存储字符串与值之间的对应关系。
ll 只能存64位,对于所给的六种运算,只有乘法有可能溢出。故对乘法采用快速乘取模的方法。将乘法变成加法,这样就不会溢出了。

AC代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
typedef long long ll;
using namespace std;
const ll mod=1LL<<47;
map<string,ll> mp;
ll mul_mod(ll x,ll y)//快速乘取模
{ll ans=0;while(y){if(y&1) ans=(ans+x)%mod;y>>=1;x=(x+x)%mod;}return ans;
}
int main()
{ios::sync_with_stdio(false);string a,b,c;while(cin>>a>>b){if(a=="def"){ll x;cin>>x;mp[b]=x;cout<<b<<" = "<<x<<endl;continue;}cin>>c;if(a[0]=='a'){mp[b]=(mp[c]+mp[b])%mod;cout<<b<<" = "<<mp[b]<<endl;}else if(a[0]=='s'){mp[b]=(mp[b]-mp[c]+mod)%mod;cout<<b<<" = "<<mp[b]<<endl;}else if(a[0]=='d'){mp[b]/=mp[c];mp[b]=(mp[b]+mod)%mod;cout<<b<<" = "<<mp[b]<<endl;}else if(a=="mod"){mp[b]%=mp[c];cout<<b<<" = "<<mp[b]<<endl;}else{mp[b]=mul_mod(mp[b],mp[c]);cout<<b<<" = "<<mp[b]<<endl;}}return 0;
}