Imtiaz.axi's blog

Long long division.
By Imtiaz.axi, history, 9 months ago, In English

In last div 3 round in C-LR i had a problem for deviding a big nunmber with a small one. I am new to programming. Note: i tried unsigned long long x; but still same

#include<bits/stdc++.h>
#define ll long long
#define str string
#define fori(i,a,N) for (int i=a;i<N;i++)
using namespace std;
vector<int> prefix(vector<int> arr) {
    int n = arr.size();
    vector<int> ps(n);
    ps[0] = arr[0];
    for (int i = 1; i < n; i++) {
        ps[i] = ps[i &mdash; 1] + arr[i];
    }
    return ps;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int N,M;
        cin>>N>>M;
        vector<int>A(N);
        string S;
        ll x=1;
        for(int i=0;i<N;i++){
            cin>>A[i];
            x*=A[i];
    }
        cin>>S;
        cout<<x%M<<" ";
        int l=0,r=N-1;
        fori(i,0,N-1){
        if(S[i]=='L'){
            x/=A[l];
            l++;
            cout<<x%M<<" ";
        }
        else if(S[i]=='R'){
            x/=A[r];
            r--;
            cout<<x%M<<" ";
        }
        }
        cout<<endl;
    }
   
}

Here when the value of x becomes more than 10^20, dividing it with numbers like 34,57 or any small type number doesnt give correct output.for that x%M is also comes wrong.what should i do? And also is the code logic correct? I know it will always bottle neck if inputs are big numbers. But for small numbers what do i have to modify?  

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

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by Imtiaz.axi (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Range of long long is around (-1e18 to 1e18). And the product of elements in the array can go much beyong the limit resulting in overflow.

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

    I tried unsigned long long. Still same problem. The problem isnt finding value of x but when dividing it with a small number. The problem is like 4/3 here even if save the value in double only int value will be saved or just 1 so for correction 4/3.0 o think my code has the same problem. Some time ago i ran into same problem but saw someone use 1LL*...... I mean multiplied with 1LL.i dont know wjat this term is, maybe for condition like 4/3.0

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

long long datatype can hold only upto 10^18. if the value goes above the limit it leads to overflow and will not produce the expected output.

→ Reply
»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Since $$$ab\equiv(a\bmod p)(b\bmod p) \pmod p$$$, You can simply do the modulo while multiplying those numbers

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

    Can you give a sample code?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      like this:

      int mul=1;
for(int i=0;i<n;++i){
    mul=mul*a[i]%m;
}
cout<<mul<<endl;

      Notice that you don't even need a long long

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

        Wait, are you giving code based on just my code or did you saw the actual problem. If you havent seen the problem its round 927 div 3 C-LR remainders

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

          For the problem, the solution is that you need to do it reversedly. Then the divisions will become multiplying, and doing modulos is ok.

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

          I just wanted to say how to get a modulus of a huge production.

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

    And that's the point of this problem: you can't simply do the division to simulate the process

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

      I know. But if i ran into same problem like dividing a great number with a small one I wnat to know how do i do the division correctly

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Imtiaz.axi (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The range of the elements in $$$A$$$ go upto $$$10^4$$$ and there can be $$$2 \times 10^5$$$ elements, so the product can go upto $$$(10^4)^{2 \times 10^5}$$$, which is well beyond anything any data type could store, storing the products of the elements modulus M doesn't help much either since once the product becomes zero, recovering the original product back by dividing will not help, to do so you will need to keep track of the factors of M in your current product, which is way too complicated.

Alternately you can simulate the entire process in reverse order, I suggest checking the top submissions. Storing the product of modulus will be a simple modular arithmetic problem if you simulate in reverse order. I think the position of task 3 and 4 should have been swapped in the last div 3 contest.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thats because the product of all numbers is too large , worst case scenario all elements are 10^4 and that would be a product of (10^4)^(10^5)=10^(4*10^5) , a number with 400000 digits!

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

    I know that. I want to know just how to do it my way

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you really want to deal with the actual (unmodded) product of the numbers, you should consider writing/using a bigint implementation.

However in these problem, it is sufficient to use some facts about modular arithmetic, and in particular, about modular inverses.

Basically, if you have a modulus $$$m$$$ and a residue $$$a$$$ modulo $$$m$$$, if $$$g = \gcd(a, m)$$$, by Bezout's theorem, there exist $$$a', m'$$$ such that $$$aa' + mm' = g$$$. Equivalently, taking everything mod $$$m$$$, we get that there exists $$$a'$$$ such that $$$aa' \equiv g \pmod m$$$. In the case $$$g = 1$$$ (i.e., $$$a$$$ and $$$m$$$ are coprime), we have $$$aa' \equiv 1 \pmod m$$$. You can show that $$$a'$$$ is unique modulo $$$m$$$, and this residue is called the inverse of $$$a$$$ modulo $$$m$$$.

Now here's how it is important for us: let's say we have the residue of $$$x = ab$$$ modulo $$$m$$$ (where $$$a$$$ is coprime to $$$m$$$), and we want to recover the residue of $$$b$$$ modulo $$$m$$$. Then we have $$$a'x = a'ab \equiv b \pmod m$$$, so $$$a'$$$ is $$$1/a$$$ modulo $$$m$$$ in the sense that division by $$$a$$$ is the same as multiplication by $$$a'$$$.

So whenever you want to divide by $$$a$$$, you multiply by $$$a'$$$. But how do you get $$$a'$$$? There are two common methods of doing this:

  • Note that our proof of existence of $$$a'$$$ was constructive — we can construct $$$a'$$$ and $$$m'$$$ using the extended Euclidean gcd algorithm.
  • Another way is to use Euler's theorem: $$$a^{\phi(m)} \equiv 1 \pmod m$$$ for $$$a$$$ coprime to $$$m$$$, so multiplying $$$a'$$$ both sides gives us $$$a^{\phi(m) - 1} \equiv a' \pmod m$$$, and thus we can raise $$$a$$$ to the power of $$$\phi(m) - 1$$$ by binary exponentiation modulo $$$m$$$ and get $$$a'$$$.
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Long long can only hold up to $$$10^{18}$$$, but there is a test case which your long long must hold $$$10000^{200000}$$$ :)

→ Reply