Home > Software engineering >  what will be the value of (a*b*c )%k?
what will be the value of (a*b*c )%k?

Time:12-16

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 ?

CodePudding user response:

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.

  • Related