【Henu ACM Round #13 C】 Ebony and Ivory
【链接】 我是链接,点我呀:)
【题意】
【题解】
先求出c-b*x的所有可能 ->存在map里面 然后枚举y看看a*y在不在map里面 在的话就有解。 这样复杂度是$O(N*log_2N)$的 比直接两层循环枚举的$O(N^2)$复杂度要来的好 这种方法也叫"中途相遇法"【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c;
map<int,int> dic;
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> a >> b >> c;
for (int i = 0;i <= 10000;i++){
if (c-b*i<0) break;
dic[c-b*i]=1;
}
for (int i = 0;i <= 10000;i++)
if (dic[a*i]){
cout <<"Yes"<<endl;
return 0;
}
cout <<"No"<<endl;
return 0;
}