Vấn đề MODULO


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 10M

Author:
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.