Блог пользователя t3rminated

Автор t3rminated, история, 7 лет назад, По-английски

In this question isn't it enough to check the gcd(A,B) divisibility with each number? i am getting wrong answer!

code--

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//utility function to find the GCD of two numbers
ll gcd(ll a, ll b)
{
    return (a%b == 0)? abs(b) : gcd(b,a%b);
}
 
int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--)
	{
	    ll n, x, y;
	    cin >> n >> x >> y;
	    ll gdc = gcd(x,y);
	    ll a[n+1];
            ll c  =0;
	    for(int i = 0; i < n; i++)
	    {
	        cin >> a[i];
	        if((a[i]%gdc == 0))
	        c++;
	        
	        
	    }
	    cout << c << " " << n-c << "\n";
	    
	}
	return 0;
}

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If we have an equation ax+by = c and if gcd(a,b) divides c, it means the equation will have integral solution however it doesn't state x,y will be positive, We want only positive x,y in this question. For instance 7x+5y = 2 doesn't have a solution where x,y are >= 0 whereas your code will count it as a valid cash payment.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    so what is the proposed solution?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      We can formulate this question as reachability problem. Initially push 0 in the queue, each time you pop an element from the queue push, (val+a,val+b) in the queue till val+a,val+b are <= 1e5,

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        but wouldn't the time complexity be too high! like for each element iterating till val+a<=100000

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          NO, we don't iterate for all val+a < 1e5 rather we incrementally see what all values can be reached.

          Spoiler
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Yeah this looks good!

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              So it's complexity will be O(n*t*logn) because for each element we can binary search in the queue whether it's found

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Binary Search? No, We run this as a pre-processing step and then answer in O(1) using 'ok' array.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

the symbol ll is it for container ?