Le concours typique AtCoder (ATC) est un concours qui pose des questions typiques dans la programmation compétitive. Merci, AtCoder.
AtCoder Typical Contest 002 B - n^p mod m
Ce thème, méthode carrée répétée Ruby Par exemple, lors du calcul de 2 à la puissance 64, si vous multipliez simplement par 2, vous devez multiplier 63 fois, mais en utilisant le résultat du calcul, vous pouvez calculer en multipliant 6 fois, ce qui conduit à un calcul plus rapide.
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
La méthode des carrés itératifs est une application de ceci aux puissances impaires et aux diviseurs.
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)
Si vous en faites une fonction, vous pouvez l'utiliser pour des concours ultérieurs ~~ copier ~~.
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))
Le suffixe sera après avoir étudié un peu plus. 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";
Pour * Perl *, cela ne semble pas causer d'erreur dans la portée de $ 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 | |
|---|---|---|---|---|
| Longueur du code | 183 Byte | 217 Byte | 227 Byte | 386 Byte |
| Temps d'exécution | 7 ms | 17 ms | 3 ms | 106 ms |
| Mémoire | 1788 KB | 3060 KB | 640 KB | 24020 KB |
Recommended Posts