How to optimize the code for modular exponentation, to make the program run faster?

Question

I have assignment in college to make the program in C++ for computing modular exponents.
The task is:

Input:
In the first line of input is an integer t (1<=t<=100000) is given which specifies the number of tests. Each test is given by three integers: a, b, m as defined above (1<=a<=109, 0<=b<=109, 1<=m<=106).
Output:
You should write t lines, the answer to the query: (ab)%m.
Example
For the input data

2
3 2 10
4 3 10

the correct answer is

9
4

And my code is:

#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
for (int i=0; i<t; i++)
{
int a,b,m;
long long int x, result = 1;
cin >>a>>b>>m;
x=a;
do
{
x%=m;
if (b&1)
{
result*=x;
result%=m;
}
x*=x;
}
while (b>>=1);
cout <<result<<endl;
}
return 0;
}

And my question is how to optimize this code, because it is running correctly but my teachers program (online Themis - an on line problem judge) is saying that "time limit exceeded" and i can't pass. So i have to do something that help the program counted faster.

Answer 1

There is a great Khan Academy article about optimizing this. You need to implement it in code
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

Answer 2

How it will be in code? I have to change all my code or just optimize this one? What will be the best?

Answer 3

Since these are different approaches, you will need to re write your code.

Answer 4

Thanks:) solved