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
N<k when ,root(N,k) = N, otherwise ,root(N,k) = root(N',k).N' by N Of k The sum of the digits in decimal notation . Input x,y,k, Output root(x^y,k) Value ( here ^ For the power of , It's not XOR ),2=<k<=16,0<x,y<2000000000, Half of the test sites x^y It will overflow int The scope of the (>=2000000000)
Input description
Each set of test data consists of one line ,x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)
Output description
`  Input may have multiple sets of data , For each set of data ,root(x^y, k) Value  Input `
`4 4 10 Output `
`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

1. 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). ...

2. Fast power modulus &amp; 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))\% ...

3. 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 ...

4. 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 ...

5. 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 ...

6. 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 ...

7. 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 ...

8. 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 . ...

9. poj 3980 Modulus operation

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

## Random recommendation

1. 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 ...

2. 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 ...

4. 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 ...

5. 《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 ...

6. 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 ...

7. 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 ...

8. 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 ...

9. 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 ...

10. 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 ...