Fonction de puissance en Java
Shofiya Bootwala
Étant donné un nombre et son inverse. Trouvez ce nombre élevé à la puissance de son propre inverse. Remarque : Comme les réponses peuvent être très volumineuses, imprimez le résultat modulo 10 9 + 7.
class Solution
{
long power(int N,int R)
{
if(R==0){
return 1%1000000007;
}
else if(R%2==0){
return power((N*N)%1000000007,R/2)%1000000007;
}
return (N%1000000007)*power((N*N)%1000000007,R/2)%1000000007;
}
}
Quand j'exécute ce programme pour 12 élevé à la puissance 21, il renvoie 0. Comment puis-je résoudre ce problème ?
Aayush Saini
Utilisez Modular Exponential pour trouver la puissance du nombre donné. prenons un exemple Power(2,5). La représentation binaire de 5 sera 0101. Chaque fois qu'un bit défini est trouvé, multipliez le résultat avec une puissance de 2 et continuez d'augmenter la puissance de 2 et divisez le nombre par 2.
La complexité temporelle de cette approche : O(logie)
static long power(long x, long y, int p)
{
long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
if (x == 0)
return 0; // In case x is divisible by p;
while (y > 0)
{
// Checking the set bit of the number
if ((y & 1) != 0)
//res=(res%p*x%p)%p this is also valid for efficient solution
res = (res * x) % p;
// Divide the number by 2
y = y >> 1;
x = (x * x) % p;
}
return res;
}