CF1542B Plus and Multiply

本文主要是介绍CF1542B Plus and Multiply，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

0x0 题意：

给定正整数 \(a,b,n\)，每次可以进行以下操作：

• 把当前的数乘以 \(a\)
• 把当前的数加上 \(b\)

假设你最开始有一个数 \(1\)，求进行若干次操作后能否把这个数变成 \(n\)。

0x1 解:

经过若干次操作后，\(1\) 一定会变成 \(((1+p_1×b)×a^{q_1}+p_2×b)×a^{q_2}+ \cdots\) 的形式。

我们把 \(1\) 和所有的 \(b\) 拆出来，那么我们就得到了 \(p×b+a^q=n\)，且 \(p,q\geq0\)，枚举 \(q\) 判断是否符合要求即可。

特判掉 \(a=1\) 的情况 (因为枚举 \(q\) 会造成死循环)。

0x2 码：

少见的正常马蜂

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long

inline int qread(){
	int tmp=0;char buf=getchar();bool f=true;
	while(!isdigit(buf)){if(buf=='-')f=false;buf=getchar();}
	while(isdigit(buf)){tmp=tmp*10+buf-'0';buf=getchar();}
	return f?tmp:-tmp;
}


bool chk(int nw,int div,int sub){
	if(div==1)return (nw-1)%sub==0;
	for(int i=1;i<=nw;i*=div){
		if((nw-i)%(sub)==0){
			return true;
		}
	}
	return false;
}


signed main(){
	int t=qread();
	while(t--){
		int n=qread(),a=qread(),b=qread();
		if(chk(n,a,b))puts("Yes");
		else puts("No");
	}
	return 0;
}

这篇关于CF1542B Plus and Multiply的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！