Exponential problem

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

dang7rickroll , stack_queue_4977 , medusa

Dạng bài

Ngôn ngữ cho phép

C, C++, Clang, Clang++, Cobol, D, ~~Groovy~~, Haskell, JS, Lua, Node JS, ObjectiveC, Output, Pascal, Prolog, Scala

Điểm: 200 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai số nguyên dương \(a\),\(m\).

Tính giá trị biểu thức \(X = a^1 \times a^2 \times ... \times a^m\)

Constraints

\(a,m \le 10^6\)

Subtask 1 [30%]

\(a,m \le 10\)

Subtask 2 [70%]

Không ràng buộc gì thêm.

Input

Dòng 1: \(t\) \((t \le 100)\) - số câu hỏi.
\(t\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(a\),\(m\).

Output

\(X \mod (10^9 + 7)\)

Example input

1
2 3

Example output

Bình luận

0

huyhau6a2 8:02 p.m. 26 Tháng 9, 2022

M 10^6 vẫn brute force được mà ad!

0

dang7rickroll 8:41 a.m. 27 Tháng 9, 2022

ông cháu brute-force xem thử có AC ko chứ tôi cũng ko biết nữa :))

0

doanngocgiahung2013 2:31 p.m. 9 Tháng 7, 2024

cho thêm python vô ik 🙁

0

huyhau6a2 12:48 p.m. 27 Tháng 9, 2022 ← chỉnh sửa 2 →

Wao có query! Không để ý. Mà c++ chắc dư sức!

Tầm này lên m<=10^7 thì chịu

10^7 c++ vẫn ac nha bạn

Hint

lũy thừa nhị phân + số học

code

#include<bits/stdc++.h>
#define ll long long
#define db double
#define str string
#define fi first
#define se second
#define mod 1000000007
using namespace std;
ll luythuanhiphan(ll a,ll t)
{
    if(t==0) return 1;
    ll k=luythuanhiphan(a,t/2);
    if(t%2==0)
    {
        return ((k%mod)*(k%mod))%mod;
    }
    return ((((k%mod)*(k%mod))%mod)*(a%mod))%mod;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t,a,m;
    cin>>t;
    while(t>0)
    {
        t--;
        cin>>a>>m;
        cout<<luythuanhiphan(a,(m+1)*m/2)<<endl;
    }
}

0

huyhau6a2 12:47 p.m. 27 Tháng 9, 2022 ← chỉnh sửa 2 →

Đặt biến tạm x để tính a^i, với mỗi lần nhân kq lên x. Độ pt O(m)

2 bình luận nữa