-1

i have searched it everywhere, i only find the solution for (ab)%k which is ((a%k)(b%k))%k.

i want to write the code for it . suppose i have been given an array of numbers a1 ,a2 , a3 , a4 ... , an. i have to find whether product of numbers any subset from the array is divisible by k .

if(ai *aj .. *am %k == 0) return true;

i want the code in c++.

i have tried the code :

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main() {
      ll t; 
      cin >> t;
      while(t--)
      {
          ll n , k ;
          cin >> n >> k;
          vector<ll>a;
          ll product = 1;
          int flag =0;
          for(ll i =0 ; i < n ; i++)
          {
              int p;
              cin >>p;
              a.push_back(p);
              if(p % k == 0)
              {
                  flag = 1;
              } 
              p = p%k;                          ................................(eqn 1)
              product = product * p;
              product = product %k;             .................................(eqn 2)
          }
          if(flag == 1)
          {
              cout << "YES" << "\n";
              continue;
          }
          product = product %k;                ...............................(eqn 3)
          if(product == 0)
          {
              cout << "YES" << "\n";
          }
          else
          cout << "NO"<< "\n";
         
      }
    return 0;
}

This code passes all the test cases . if i remove the equation 1 from the code , it will pass all the testcases after it also . but if i remove the equation 2 , the code gives it as wrong answer. https://www.codechef.com/problems/DIVBYK

Can you tell me the concept behind it ?

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
Sarraayush
  • 49
  • 5
  • 4
    At a guess both are intended to stop the number from overflowing – Alan Birtles Dec 15 '22 at 06:33
  • 1
    `a*b*c = d*c`, where `d=a*b`. This should allow you to simplify the equation. – VLL Dec 15 '22 at 06:35
  • Ask yourself: If I multiply any integer with 3, will the result be dividable by 3? If I multiple that result by any other integer, will the results of that be dividable by 3? What does that mean in the case that I find any array members which are dividable by k? – Yunnosch Dec 15 '22 at 07:11
  • 1
    Did you click yourself on the link in your question? Does what happens match your expectation? I doubt it. – Yunnosch Dec 15 '22 at 07:22
  • 2
    Where are you learning C++ from ? The first three lines of your code are ALL bad practices and should not be used. Competitive coding sites like leetcode, codechef should not be used for learning c++ (just to train your problem solving skills). Learn C++ from [books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/ – Pepijn Kramer Dec 15 '22 at 08:03
  • For that codechef challenge thinking of `(ab)%k which is ((a%k)(b%k))%k` is overthinking it. The only thing you need to know is whether any member is dividable. Any subset which contains at least one dividable member has a dividable product. E.g. you cannot multiply 6 with any positive integer and get a result which is NOT dividable by 3. This does not strictly answer the question as asked. But you should see that you should not ask that question. Compare https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem – Yunnosch Dec 15 '22 at 10:55

1 Answers1

3

The concept is that for a1,a2,b1,b2 satisfying:

a1 == b1   (mod k)
a2 == b2   (mod k)

it holds that

a1*a2 == b1*b2    (mod k)

In other words, the remainder of multiplying two numbers is the same as the remainder of multiplying just the remainders of the original numbers.

This is very handy because the latter does not suffer from overflow if k<sqrt(largest_representable_number).

One can prove by induction the same for product of N numbers.

Quimby
  • 17,735
  • 4
  • 35
  • 55