rahul_bhaiya_sabka_baap's blog

GCD and Subsequence Problem
By rahul_bhaiya_sabka_baap, history, 6 years ago, In English

Given an array of size N and an integer K. You need to find the (sum of subsequence * GCD of that subsequence) over all K length subsequences of the given array A. Print the answer modulo 998244353. For e.g. A[] = {1, 2}, K = 1. Two subsequences of length 1 are {1} and {2}, then answer is 1*1 + 2*2 = 5

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

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What are the constraints? Also, is this problem available in an online judge?

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

I think this can be solved using mobius inversion.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, inattentive, solved another problem =)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry, I can not understand how changes of GCD are common to subsequence GCD — it is not subarray. Maybe I am wrong, but please explain it further if you can :)

    My idea for solution:

    You can run next DPi — sum over all subsequences with GCD equal to i. Now you can find easily how many integers are divisible by i — that number can be x ( it can be checked by sieve or factorization of all numbers). So possible amount of subsequences is . In how many subsequences we will have some fixed integer y divisible by i. We will have it in . So, contribution of number y is y· . Now you do not know is that GCD exactly i or you chose some numbers and their GCD is bigger than i (it can be 2·i, 3·i...). So you should decrease your value for values DP2·i, DP3·i... After it you got real value for DPi and can calcualte answer for i - 1.

    Final result is next sum: .

    Complexity of solution O(n·logn)

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

      Did the exact same thing, but got WA, not even a single file passed. Tried to debug for around an hour, couldn't find a mistake, then I thought maybe there's a flaw in this approach that I'm unable to see.

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

        You can share code, in case I see mistake in your solution or approach I will tell you :)

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

          I wish I could, but I'm not saving codes due to very unreliable laptop, it's having hard disk issues right now, and creates problems like not starting up, or not shutting down without force, so I have to format it every now and then, it works well for a while and the same thing all over again :/

          I tried to find my submissions, but Hackerearth doesn't allow seeing your submissions in a test format contest, or maybe there's a way that I don't know about.

          Nevertheless, thanks for offering to help and sharing your approach, now I feel confident that my approach was right :)

          → Reply