** The power of dichotomy **

int getMi(int a,int b)

{

int ans = ;

while (b != )

{

// When the binary bit k Position as 1 when , It's a long ride a Of 2^k Power , And then use ans preservation

if (b % == )

{

ans *= a;

}

a *= a;

b /= ;

}

return ans;

}

** Fast modular exponentiation **

The formula ：

The final version of the algorithm ：

int PowerMod(int a, int b, int c)

{

int ans = ;

a = a % c;

while(b>)

{

if(b % = = )ans = (ans * a) % c;

b = b/;

a = (a * a) % c;

}

return ans;

}

** seek Root(N,k)**

**Title Description**

**Input description**

**Output description**

Input may have multiple sets of data , For each set of data ,root(x^y, k) ValueInput

4 4 10Output

4

Code ：

#include <cstdio>

#include <math.h>

#include <cstring>

#include <algorithm> //root(x*y,k) = root(root(x,k)*root(y,k),k) int Root(int N,int k)

{

if(N<k)return N;

int ans = ;

//N Greater than k, seek N by k The sum of all of you

while(N != ){

ans += N%k;

N /= k;

}

return Root(ans,k);

} int getAns(int x,int y,int k)

{

int num = Root(x,k);

int ans = ;

while(y > ){

if(y%){//y It's odd

ans = Root(ans*num, k);

}

y /= ;

num = Root(num*num, k);

}

return ans;

} int main()

{

int x,y,k; while(~scanf("%d %d %d",&x,&y,&k)){

printf("%d\n",getAns(x,y,k)); } return ;

}

## The power of dichotomy / Fast modular exponentiation ——root(N,k) More articles about

- A^B mod C ( Fast power + Fast ride + modulus ) Answer key
A^B mod C Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63). ...

- Fast power modulus & Fast multiplication and modulus
Fast power modulus That is to find out (a^b)mod c Value . Because when a.b When the value of is very large, we can directly find a^b May cause overflow , And it's inefficient . Ideas The principle is based on \(a*b \% c = ((a \% c)*(b \% c))\% ...

- Divide two numbers, Divide two numbers to find quotient , You can't multiply , division , Modulus operation
Problem description : Seeking quotient , You can't multiply , division , Modulus operation . Algorithm ideas : You can't use division , That's just subtraction , But with subtraction , Overtime . You can use displacement operations , Every time the divisor moves left , amount to 2 times . public class DividTwoInteger ...

- a ^ b mod c Reflection on the optimization of modular operation （ old person ）
This is a journal that mocks me for using clumsy and stupid ideas to solve problems . RSA Encryption and decryption involve a ^ b mod c The problem of , How to calculate this value ? I will choose pow(a, b) % c, In fact, I'm writing RSA When ...

- java Modulus operation % In fact, it takes the remainder sketch Example Application in database sub database sub table
java Modulus operation % In fact, it takes the remainder sketch Example Application in database sub database sub table Modulus operation Modular operation is different from complement operation .“ model ” yes “Mod” transliteration , Modular operations are mostly used in programming . Mod The meaning of redundancy . Modular operations in number theory and programming ...

- HDU 4549 Matrix fast power + Fast power + Euler function
M Fibonacci sequence Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Sub ...

- HDU——1395 2^x mod n = 1（ Modular algorithm ）
2^x mod n = 1 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) To ...

- javascript How does modulo work ？ It's actually taking the remainder
Ask whether to divide , Record the mold removal here such as 120 Is the minute on the hour ?120%60 === 0 For the whole point javascript Modulo is the value of one expression divided by the value of another , And return the remainder . Take the mold in js It means to take the remainder . ...

- poj 3980 Modulus operation
Modulus operation Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10931 Accepted: 6618 Description ...

## Random recommendation

- Hbase Learning notes 01
Recently, I have come into contact with you in the project HDFS.mapreduce as well as Hbase, There's a real chance , Today I'm going to sum up this knowledge , For a rainy day . First of all, from the Hbase Let's get started . Hbase It's based on HDFS Distributed database on , The picture below is Hb ...

- iOS： According to the log to locate the network request, the error is caused by the server , It's the client side ？
One . Introduce In project development , The cooperation between server and client is particularly important , One of the most important links to connect them is network request , For the server , If something goes wrong in this link , So security is out of the question , And for clients , If there is an error in this module ...

- Unity3D Multi-Compile Shader
http://www.martinpalko.com/muli-compile-unity/ http://forum.unity3d.com/threads/tutorial-shade-more- ...

- php in session Usage of
PHP Medium session By default, the client is used Cookie. When the client Cookie When disabled , Will automatically pass through Query_String To pass on . Php The functions that handle the session are 11 individual , Let's go into a few more details ...

- 《A First Course in Probability》-chaper5- Continuous random variable - The distribution of functions of random variables
In discussing the distribution of continuous random variable function , From the general situation ( In the article on normal distribution ), Can get a simplified version of the model . Recall the process of using the relationship between distribution function and probability density to solve the function distribution of random variables , Yes Y=g(x), If g(x) It's strictly single ...

- Spark1.0.0 Monitoring methods
Spark1.0.0 We can do it in the following ways Spark Application monitoring : Spark Application's WebUI perhaps Spark Standalone Cluster monitoring indicators , Then through the cluster monitoring of support metrics collection ...

- Talking about iOS The video shows N Kind of solution
Jane Register login Add the attention author Maru2016.03.22 20:46* Yes 4349 word , By 135 People's attention , To obtain the 207 I like it Number of words 1621 read 2895 Comment on 43 like 159 header ...

- Weekend study notes ——day03（ modular , package ）
One , review ''' Decorator @wraper # fn = wraper(fn) def fn(): pass def wrap(arg): def outer(func): # It can be used arg def i ...

- Highlights | GIAC The conference PPT+ Video collection full broadcast ！
GIAC It is a grand event in the field of Internet technology in China , Every year from the Internet architecture to the most popular system architecture design . Artificial intelligence . machine learning . Engineering efficiency . Blockchain . There are typical cases of technological innovation and R & D practice in the field of distributed architecture , Share their most ...

- python Get the file name of a specific format in the specified directory
Always used before windows Under the bat The script gets the file name of the specified format in a directory , As shown below : dir *.jpg /b/s > train.set pause Very simple , Put this bat Put the file where you want to get the file ...