Select solution language
Write solution here.
# Complex Multiplication
## Idea
The β« data type in C++ can hold values no smaller than β231 and no larger than 231β1, where 231 is around 2β
109. This means that if we try to multiply a and b, we will overflow and get the wrong answer (did you end up with a negative answer?).
Thankfully, C++ has the longlong data type, which can hold values from β263 to 263β1. Do not use the long data type, since C++ doesn't require a long to be as big as longlong (which is 64 bits. β« is 32 bits). There are a few ways to achieve this. We can read the input as 64-bit integers like so:
longlonga;longlongb;cββͺaβͺb;
Since longlong is pretty difficult to type, we can put this as the top of our code to make it shorter:
usingll=longlong
This tells the C++ compiler to replace every instance of ll with longlong, so we can instead write the input as
lla;llb;cββͺaβͺb;
The other way is to cast the value of ab to a long long. In C++, when you do an operation on two numbers a and b, where one of them is a long long and the other is an int, C++ will cast the result to a long long, and there will be no overflow.
For example
β«a=2000000000;longlongb=2000000000;coutβ©a+bβ© β©aβ
bβ©\n;/Β¬hβgwilloverflow!
This doesn't mean you read in a as an integer and b as a long long, though you can do that. We can just cast a to a longlong before we multiply, as follows:
1LLβ
aβ
b
Why does this work? Well, if we just do 1β
aβ
b this will run without any issues. 1LL is just our way of telling the C++ compiler to multiply a by 1 that's a long long data type. This will cast the product ab into a long long, since as said before, when C++ does an operation between an int and a long long, the resulting value is a long long. Don't forget to take the product modulo c at the end.
## Code
#βclude<bitsstdc++.h>usingnamespacestd;usingll=longlong;constβ«MOD=1E9+7;constβ«INF=1E9;constllINFLL=1E18;β«a;β«b;β«c;β«maβ(){iosbase::syncwithstdio(false);cβ.tie(0);cββͺaβͺbβͺc;coutβ©(1LLβ
aβ
b)%cβ©\n;}