做网站的法律,网页设计制作网站首页,建筑设计有哪些专业,广告在线设计制作原题链接#xff1a;Problem - 1542B - Codeforces
题目大意#xff1a;初始集合里面只有1#xff0c;给a和b#xff0c;可以对集合里面的数x进行二种操作#xff0c;x*a#xff0c;xb,并放入集合#xff0c;给数n#xff0c;问集合里面会不会产生n#xff0c;会就输…原题链接Problem - 1542B - Codeforces
题目大意初始集合里面只有1给a和b可以对集合里面的数x进行二种操作x*axb,并放入集合给数n问集合里面会不会产生n会就输出yes不会就输出no。
思路如果n会出现在集合里面那么他一定是由a^c1c2*b这种形式c1和c2为未知数如果进行操作1那么就会对数进行乘a的操作因为初始只有1那么必定会产生a^c1这种数如果进行了操作2那么就会加上b如果继续操作2那么就会变成2b如果操作1那么就会变成ab但是肯定可以提出一个公因子b然后将另一部分看为c2。因为c1是操作1的操作数而且2^641e16所以可以直接从小到大枚举c1。
//冷静冷静冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize(O3)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e610,mod998244353;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll t;cint;while(t--){ll n,a,b;cinnab;ll now1,f0;if(a1) {if((n-1)%b0){coutYesendl;}else coutNoendl;continue;}while(nown){if((n-now)%b0)//如果a^c1已经减完了那么剩下的数是b的倍数{f1;break;}now*a;//a^c1}if(f)coutYesendl;else coutNoendl;}return 0;
}
