AtCoder Beginner Contest 169 A I will explain the problem "Multiplication 1".
Problem URL: https://atcoder.jp/contests/abc169/tasks/abc169_a
Given the integers $ A $, $ B $. Find $ A x B $.
・ $ 1 \ leq A \ leq 100 $ ・ $ 1 \ leq B \ leq 100 $ ・ All inputs are integers
You can implement it according to the problem statement. Below are examples of solutions in Python3, C ++, and Java.
{A169.py}
x,y = map(int,input().split())
print(x*y)
{A169.cpp}
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
cin >> x >> y;
cout << x * y << endl;
}
{A169.java}
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner (System.in);
int x = scan.nextInt();
int y = scan.nextInt();
System.out.println(x*y);
}
}
Find $ X × Y $. However, the restrictions are as follows. ・ $ 1 \ leq X \ leq 10 ^ 5 $ ・ $ 1 \ leq Y \ leq 10 ^ 5 $
In the case of Python3, the value that can be handled by int type is infinite, so it's okay, but
Let's try the C ++ solution example code for the maximum constraint of this problem.
input
{input.txt}
100000 100000
output
{output.text}
1410065408
Originally, it is $ 10 ^ 5 x 10 ^ 5 = 10 ^ {10} $, so I think many people think that it doesn't look like this </ b> ...
This is a phenomenon that occurs in overflow </ font> </ b>, which is a language that is restricted by values that can be expressed by int type, such as C ++ and Java.
Dividing $ 10 ^ {10} $ by $ 2 ^ {31} $ yields a remainder of $ 1410065408 $.
C ++ and Java int types can represent values from $ -2 ^ {31} $ to $ 2 ^ {31} -1 $. Therefore, since the product of int type and int type is int type, such overflow occurs. </ b>
In C ++, for example, using long long int
increases the values that can be expressed.
The values that can be represented by long long int
are $ -2 ^ {63} $ to $ 2 ^ {63} -1 $.
Therefore, you can avoid the above problem by writing the following code. </ font>
{Overflow measures.cpp}
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int x,y;
cin >> x >> y;
cout << x * y << endl;
}
{output.text}
10000000000
AtCoder problem statements and samples sometimes have notations such as Beware of overflow
</ b> and 32bit integers may not fit in .
</ b>. There is.
In such cases, doubt </ b> whether the variable type is long long int
before submitting.
Extra WA (incorrect answer) will be created and a penalty of 5 minutes will occur .... </ font>
Recommended Posts