guptaji30's blog

how to approach adhog , basic math questions ?
By guptaji30, history, 3 years ago, In English

I was giving this round https://mirror.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

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B could have been solved if you just knew, $$$gcd(a,b)=gcd(a,b-a)$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how ? can you be a bit more elaborate

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Could you provide some proof for why you think this condition is not sufficient? My solution based on just that one equation got accepted.

            → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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... ?

        → Reply