Der AtCoder Typical Contest (ATC) ist ein Wettbewerb, der typische Fragen in der Wettbewerbsprogrammierung stellt. Vielen Dank, AtCoder.
AtCoder Typical Contest 002 B - n^p mod m
Dieses Thema wiederholte quadratische Methode Ruby Wenn Sie beispielsweise 2 mit der 64. Potenz berechnen und einfach mit 2 multiplizieren, müssen Sie 63-mal multiplizieren. Wenn Sie jedoch das Berechnungsergebnis verwenden, können Sie durch 6-fache Multiplikation berechnen, was zu einer schnelleren Berechnung führt.
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
Die iterative Quadratmethode ist eine Anwendung auf ungerade Potenzen und Teiler.
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)
Wenn Sie es zu einer Funktion machen, können Sie es für spätere Wettbewerbe verwenden ~~ 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))
Das Postfix wird nach dem Studium etwas mehr sein. 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";
Für * Perl * scheint es keinen Fehler im Bereich von $ m zu verursachen. 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 | |
|---|---|---|---|---|
| Codelänge | 183 Byte | 217 Byte | 227 Byte | 386 Byte |
| Ausführungszeit | 7 ms | 17 ms | 3 ms | 106 ms |
| Erinnerung | 1788 KB | 3060 KB | 640 KB | 24020 KB |
Recommended Posts