Processing math: 100%
Solutions of Complex multiplication - MarisaOJ: Marisa Online Judge

Solutions of Complex multiplication

Select solution language

Write solution here.


omegumunot    Created at    5 likes

# 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;}