Cho a và m, tính biểu thức X=a^1 x a^2 x a^3 x ... x a^m ( a,m<=10^6) kết quả là giá trị biểu thức X mod 10^9+7 Input: t (t <100) số câu hỏi a và m output: kết quả vd: input: 1 2 3 output: 64

Ý tưởng và thuật toán:

- Với a,m <= 10^3 thì chúng ta sẽ dùng cày trâu

- Với a,m <= 10 ^6 chúng ta sẽ có hướng giải quyết khác:

+ chúng ta thấy a^1 x a^2 x a^3 x ... x a^m = a^1+2+3+...+m (1)

+ chúng ta có công thức 1+2+3+...+m=m*(m+1)/2

+Vậy chúng ta Binary Exponentiation để tính lũy thừa

Code c++:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
 ll t,a,m,mod=1000000007;
 cin>>t;
 while(t--)
 {
  cin>>a>>m; 
  cout<<binpow(a,m*((m+1)/2),mod);
 }
}