Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B

Introduction

AtCoder Typical Contest (ATC) is a contest that asks typical questions in competitive programming. Thank you, AtCoder.

This theme

AtCoder Typical Contest 002 B - n^p mod m

This theme, iterative squares Ruby For example, when calculating 2 to the 64th power, if you simply multiply by 2, you need to multiply 63 times, but by using the calculation result, you can calculate by multiplying 6 times, which leads to faster calculation.

2^64.rb


n = 2
63.times do
  n *= 2
end
puts n # => 18446744073709551616

n = 2
6.times do
  n *= n
end
puts n # => 18446744073709551616

The iterative squares method applies this to odd-numbered powers and divisors.

ruby.rb


n, m, p = gets.split.map(&:to_i)
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts mpow(n, p, m)

If you make it a function, you can use it for later contests ~~ copy ~~.

Python

python.py


n, m, p = map(int, input().split())
def mpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
print(mpow(n, p, m))

The postfix if will be after studying a little more. Perl

perl.pl


chomp (my ($n, $m, $p) = split / /, <STDIN>);
sub mpow {
  my ($n, $p) = @_;
  my $r = 1;
  while ($p > 0) {
    $r = $r * $n % $m if $p & 1;
    $n = $n * $n % $m;
    $p >>= 1;
  }
  $r;
}
print mpow($n, $p), "\n";

For * Perl *, it doesn't seem to cause an error in the scope of $ m. Java

java.java


import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger n = new BigInteger(sc.next());
        BigInteger m = new BigInteger(sc.next());
        BigInteger p = new BigInteger(sc.next());
        sc.close();
        System.out.println(n.modPow(p, m));
    }
}
Ruby Python Perl Java
Code length 183 Byte 217 Byte 227 Byte 386 Byte
Execution time 7 ms 17 ms 3 ms 106 ms
memory 1788 KB 3060 KB 640 KB 24020 KB

Summary

Recommended Posts

Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Sorting AtCoder ARC 086 C hashes to solve in Ruby, Perl, Java and Python
Scraping with Node, Ruby and Python
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
AtCoder JSC2019 Qual B to solve with Ruby and Python Inverse element of arithmetic progression
List split and join strings with split and join (Perl / PowerShell / Java / Kotlin / Python)
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
AtCoder Beginner Contest 170 B Problem "Crane and Turtle" Explanation (Python3, C ++, Java)
MessagePack-Try to link Java and Python with RPC
Solving the Lorenz 96 model with Julia and Python
Solving with Ruby AtCoder ABC110 C String Manipulation
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve AtCoder 167 with python
Python and Ruby split
AtCoder ARC080 D simulation solved in Ruby and Python
Investigate Java and python data exchange with Apache Arrow
Comparison of CoffeeScript with JavaScript, Python and Ruby grammar
Version control of Node, Ruby and Python with anyenv
Programming with Python and Tkinter
Solve AtCoder ABC166 with python
Light blue with AtCoder @Python
AtCoder Beginner Contest 177 B Problem "Substring" Explanation (Python3, C ++, Java)
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Python and hardware-Using RS232C with Python-
Java VS PHP VS Python VS Ruby
Solving Sudoku with Python (Incomplete)
Python and ruby slice memo
I compared Java and Python!
Zundokokiyoshi with python / ruby / Lua
About Perl, Python, PHP, Ruby
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving Sudoku with Python (Part 2)
python with pyenv and venv
Hello World in various languages [Python / PHP / Java / Perl / Ruby]
AtCoder Beginner Contest 169 B Problem "Multiplication 2" Explanation (Python3, C ++, Java)