# Complex Multiplication
## Idea
The ```int``` data type in C++ can hold values no smaller than $-2^{31}$ and no larger than $2^{31}-1$, where $2^{31}$ is around $2\cdot10^9$. 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 ```long long``` data type, which can hold values from $-2^{63}$ to $2^{63}-1$. Do not use the ```long``` data type, since C++ doesn't require a ```long``` to be as big as ```long long``` (which is 64 bits. ```int``` is 32 bits). There are a few ways to achieve this. We can read the input as 64-bit integers like so:
```
long long a; long long b;
cin >> a >> b;
```
Since ```long long``` is pretty difficult to type, we can put this as the top of our code to make it shorter:
```
using ll = long long
```
This tells the C++ compiler to replace every instance of ```ll``` with ```long long```, so we can instead write the input as
```
ll a; ll b;
cin >> 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
```
int a = 2000000000; long long b = 2000000000;
cout << a + b << " " << a * b << "\n";
// nothing will overflow!
```
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 ```long long``` 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
```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;
int a; int b; int c;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> a >> b >> c;
cout << (1LL * a * b) % c << "\n";
}
```
omegumunot
Created at
3 likes