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.