AtCoder Typical Contest (ATC) is a contest that asks typical questions in competitive programming. Thank you, AtCoder.
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 |
Recommended Posts