【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
先求出c-bx的所有可能
->存在map里面
然后枚举y看看ay在不在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;
}