I was giving this round https://codeforces.com/contest/1542 and wasn't able to solve problem B. Though after just a small hint I was able to solve it but I can't get over the fact that I wasn't able to approach this question . are the some good resources for constructive algorithm questions or its just natural for some people ? if there are some good resources please do share them. It's not just the mentioned contest I want to improve ability to solve constructive algorithm questions in general.
thanks in advance
Problem B could have been solved if you just knew, $$$gcd(a,b)=gcd(a,b-a)$$$.
how ? can you be a bit more elaborate
Initially the set has only $$${1}$$$.
The two operations are :
1- $$$x*=a$$$
2- $$$x+=b$$$
So, for any number $$$n$$$, if $$$gcd(n,b)=1$$$ then it means we can obtain it by using 2nd operation repeatedly, since $$$gcd(b,k*b+1)=gcd(b,(k-1)*b+1)=\cdots=gcd(b,1)=1$$$
Now , if we apply operation-1 at any time, the number becomes a multiple of $$$a$$$.
Let's analyse the terms obtained in the number after doing operation-1, if we do it after 2nd operation, all terms are the multiples of $$$b$$$ except the terms like $$$a,a^2,a^3\cdots$$$, so if $$$n$$$%b = $$$a^p$$$ %b for some number p, then n is present in the set.
I don't understand why to bother about gcd, all we care about is
n — a ^ x (x >= 0) to be divisible by b right?
I can't think in terms of gcd so it feels pretty complicated to me
n — a ^ x (x >= 0) to be divisible by b
This condition is not sufficient, and I don't think you can solve it without thinking about gcd.
Edit: It's correct, I misread the overly large minus sign.
Could you provide some proof for why you think this condition is not sufficient? My solution based on just that one equation got accepted.
So, for any number n, if gcd(n,b)=1 then it means we can obtain it by using 2nd operation repeatedly,Sorry, but I don't understand this statement. If b = 3, and n = 5, then gcd(3, 5) = 1. But how can we obtain 5 by just doing 1 + b + b... ?