首页 > 其他分享 >Codeforces Round 729 (Div. 2)B. Plus and Multiply(构造、数学)

Codeforces Round 729 (Div. 2)B. Plus and Multiply(构造、数学)

时间:2024-02-13 16:55:50浏览次数:37  
标签:int Codeforces long Plus Multiply define

题面

image

链接

B. Plus and Multiply

题意

给定\(n,a,b\)
可以进行的操作

  1. \(*a\)
  2. \(+b\)

最开始的数是1
问能否经过上面的两种操作将1变为n

题解

这题的关键是能不能想出来这个集合里面的数的统一的表达形式
所有数都可以表示为
\(a^x+y * b\)
然后只要存在\(x\)和\(y\),使得\(a^x+y * b=n\)即可
对上式进行等价变换可以得到
\((n-a^x)\equiv0\quad (mod \quad b)\)
还有需要注意的是特判\(a=1\)的情况,因为\(a=1\)时会陷入死循环

代码

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=2e5+10;
int a[N];
void solve()
{
	int n,a,b;
	cin>>n>>a>>b;
	if(a==1){
		cout<<((n%b)==(1%b)?"YES":"NO")<<endl;
		return;
	}
	for(int i=1;i<=n;i*=a){
		if((n-i)%b==0){
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

总结

对数学推式子的能力还是太差,需要多练

标签:int,Codeforces,long,Plus,Multiply,define
From: https://www.cnblogs.com/cxy8/p/18014648

相关文章

  • Codeforces Round 922 (Div. 2) A~C
    A.BrickWall#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,m;cin>>n>>m;intans=n*(m/2);cout<<ans<<"\n";}intmain(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int......
  • Codeforces Round 923 (Div. 3)
    A.MakeitWhite#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ inta,b,n; strings; cin>>n>>s; for(inti=0;i<n;i++){ if(s[i]=='B'){ a=i; break; } } for(inti=n-1;i>=0;i--){ if(s[i]=='B&......
  • Codeforces Round 924 (Div. 2)
    B.Equalize与数组的原始顺序无关,直接排序,然后用双指针滑动范围a[r]-a[l]小于n#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ intn; cin>>n; set<int>st; for(inti=1;i<=n;i++){ intx; cin>>x; st.insert(x); } ......
  • Codeforces Round 924 (Div. 2)
    1928D-LonelyMountainDungeons题意:有\(n\)个种族,第\(i\)个种族\(c_i\)个生物,现在要将这些生物分成若干组,每一对不在同一组但是同一种族的生物会对这种分组的价值贡献\(b\),如果分了\(k\)组,则价值要减去\((k-1)x\),求最大价值。\(n\le10^5,\sumc_i\le10^5\)思......
  • Codeforces Round 303 (Div. 2)C. Kefa and Park(DFS、实现)
    @目录题面链接题意题解代码总结题面链接C.KefaandPark题意求叶节点数量,叶节点满足,从根节点到叶节点的路径上最长连续1的长度小于m题解这道题目主要是实现,当不满足条件时直接返回。到达叶节点后统计答案,用vector存图的话,无向图时,叶节点的边只有一条,也就是\(g[i].size()......
  • Codeforces Round 924 (Div. 2)B. Equalize(思维+双指针)
    目录题面链接题意题解代码题面链接B.Equalize题意给一个数组\(a\),然后让你给这个数组加上一个排列,求出现最多的次数题解赛时没过不应该。最开始很容易想到要去重,因为重复的元素对于答案是没有贡献的。去重后排序。,然后维护一个极差小于n-1的区间,,区间长度就是可能的答案......
  • Codeforces Round 924 (Div. 2)
    E-ModularSequence题意给定\(n,x,y,s\),求是否有长为\(n\)的一个数列\(\{a\}\)满足\(a_1=x\)且\(\foralli>1:a_i=a_{i-1}+y\lora_i=a_{i-1}\bmody\)且\(\sum\limits_{i=1}^{n}a_i=s\)。\(\sumn,\sums\le2\times10......
  • Codeforces Round 924 (Div. 2)
    不会F的场。ACode#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ ios::sync_with_stdio(false); cin.tie(0); intt; cin>>t; while(t--){ inta,b; cin>>a>>b; intf=0; if(a%2==0&&am......
  • Codeforces Round 924 (Div. 2)
    CodeforcesRound924(Div.2)A-RectangleCutting解题思路:初始矩形长宽为\((a,b)\),如果我们切\(a\),那么一定不能再拼接\(a\),否则一定一样。所以我们拼接\(b\),即将\(a\)对半分开得到两个\((\frac{a}{2},b)\)矩形拼接。此时,如果\(\frac{a}{2}=b\)那么拼接出来的矩形和初......
  • Codeforces Round 905 (Div. 3)
    题目链接A.先算距离,特判0的位置,最后加4#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){strings;cin>>s;s=""+s;intlast=1,now,ans=0;for(inti=1;i<s.si......