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 — 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?
Auto comment: topic has been updated by Imtiaz.axi (previous revision, new revision, compare).
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.
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
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.
Im pretty usre its around 2^64
Since $$$ab\equiv(a\bmod p)(b\bmod p) \pmod p$$$, You can simply do the modulo while multiplying those numbers
Can you give a sample code?
like this:
Notice that you don't even need a long long
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
For the problem, the solution is that you need to do it reversedly. Then the divisions will become multiplying, and doing modulos is ok.
I just wanted to say how to get a modulus of a huge production.
And that's the point of this problem: you can't simply do the division to simulate the process
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
Auto comment: topic has been updated by Imtiaz.axi (previous revision, new revision, compare).
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.
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!
I know that. I want to know just how to do it my way
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:
Hi, I have observed that modular arithmatics is a frequently occuring topic. I have very limited knowledge about it and I would like to separately work on this topic, would you be aware of any resources which can help me improve? Thanks.
There are quite a few resources on modular arithmetic that I know of:
I recommend going through the relevant parts of all of them (perhaps in this order). If you just want to go through one resource, I would recommend the first two chapters of https://artofproblemsolving.com/community/c6h2344755.
Oh my god I love you. Chad community fr, orz nor, imma get started on this right away.
Hi nor, three weeks ago I asked you for these sources. With the help of the sources you mentioned and studying different resources from the internet, especially all the sources mentioned in USACO guide and CP algo plus practicing decent amount of problems, I am now confident in the basics of modular arithmatics for CP. Felt like I owed some gratitude and hence this comment.
Long long can only hold up to $$$10^{18}$$$, but there is a test case which your long long must hold $$$10000^{200000}$$$ :)