Vấn đề MODULO

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 10M
Author:
haidv
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho số nguyên dương a, b, M, trong đó a là số rất lớn được biểu diễn như một xâu ký tự số.

Hãy tìm K = (ab ) %M. Ví dụ a = 3, b=2, M = 4 thì K = (32)%4 = 1

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 a, b, M được viết trên một dòng.

T, a, b, M thỏa mãn ràng buộc : 1≤T≤100; 0≤length(a) ≤1000; 2≤ b, M ≤1012 .

Output

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

Example

Input
2
2 3 5
3 2 4

Output
3
1

utc

Comments


  • 1
    TICHPX  commented on Sept. 10, 2021, 9:40 a.m. ← edited

    My code C++ anh em tham khảo

    #include<bits/stdc++.h>
using namespace std;
#define LL unsigned long long

LL multt(LL a,LL b,LL M)
{
    if(log10(a)+log10(b)<17) return a*b%M;
    if(a>b) swap(a,b);
    LL c=sqrt(b);    //b=c*q+r   -> a*b = a*c*q  + a*r 
    return (multt(a*c%M,b/c,M)+multt(a,b%c,M))%M;
}
void test()
{
    string x;
    LL a=0,b,M,t=1;       //tinh a=x%M
    cin>>x>>b>>M;
    for(char c:x) a=(a*10+c-'0')%M;     //tinh a^b%M;
    while(b)
    {
        if(b%2) t=multt(a,t,M); 
        b/=2; 
        a=multt(a,a,M);
    }
    cout<<t<<"\n";
}
int main()
{
    int t;
    cin>>t;
    while(t--) test();
}

  • 2
    haidv  commented on April 11, 2020, 4:46 p.m.

    bài này bị sai test a ơi


  • 1
    Nam_CNTT2_K58  commented on April 11, 2020, 4:07 p.m.

    ad sửa test cho python chạy đc cái.