Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

CPPMOD01 - MODULO 1

Cho ba số nguyên dương x, y, p. Nhiệm vụ của bạn là tính (xy ) %p. Ví dụ với x = 2, y = 3, p = 5 thì (23 )%5=3.

Input

Dòng đầu tiên đưa vào số lượng test T.

Những dòng kế tiếp mỗi dòng đưa vào một test. Mỗi test là bộ ba x, y, p được viết cách nhau một vài khoảng trống. 

T, x, y, p thỏa mãn ràng buộc : 1≤T≤100; 1≤x, y≤106 ; 1≤P≤109+7

Output

Đưa ra kết quả mỗi test theo từng dòng.

Example

Input Output
2 
2 3 5
3 2 4		3
1
Submit solution!
Được gửi lên bởi:adm
Ngày:2019-10-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP CPP14
hide comments
2020-12-07 18:16:55
#include<iostream>

using namespace std;

int pow(long long a,long long b,long long p)
{
long ret = 1;
a %= p;
b %= p - 1;
while (b > 0) //vòng l?p phân tích b thành co s? 2
{
if (b % 2 > 0) //? v? trí có s? 1 thì nhân v?i a^(2^i) tuong ?ng. T?t c? các phép nhân d?u có phép mod p theo sau.
ret = ret * a % p;
a = a * a % p; //tính ti?p a^(2^(i+1)), a^1 -> a^2 -> a^4 -> a^8 -> a^16 v.v...
b /= 2;
}
return ret;
}

int main()
{
int n;
cin>>n;
while(n--)
{
long long a,b,c;
cin>>a>>b>>c;
cout<<pow(a,b,c);
cout<<endl;
}
return 0;
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.