牛客2020寒假训练营2-G

牛客2020寒假训练营2-G

七月 15, 2020

G.拿物品

题意
t组样例 -1e9<=a b c g<=1e9
0<=d,e,f<=1e9;
判定 a ^ d+b ^ e+c ^ f==g
由于直接快速幂会爆ll

题解

原式取模的意义下，有概率成立，我们可以多取几个模提高真确率

取mod后有概率形成不冲突映射对

类hash的思路 觉得很玄学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=(ll)1e9+8;
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;y>>=1;
    }
    return ans%mod;
}
int main(){
    int t;cin>>t;
    while(t--){
        ll a,b,c,g;
        ll d,e,f;
        cin>>a>>b>>c>>d>>e>>f>>g;
        if((qpow(a,d)+qpow(b,e)+qpow(c,f))%mod==g)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}