uestc 1072 a ^ b

7826 ワード

a ^ b


Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 334 Tried: 2153


Description


aのbの次の4位を求めます.
 

Input


 
入力された最初の行はT(1000を超えない)です.Tはテスト部の個数を表し,各部は個別に計算し,要求通りに結果を出力する必要がある.次は各テストセクションです.第1行は、a b、0 

Output


 
各テストセクションについて、各質問の正解の最後の4桁を出力し、4桁未満の場合は前に0を補充してください.
 

Sample Input


 
2
2 1
3 10
 

Sample Output


 
0002
9049

Source


 
zhymaoiing
 1 #include<iostream>

 2 #include<cstdio>

 3 using namespace std;

 4 

 5 typedef long long LL;

 6 LL mod=10000;

 7 

 8 

 9 LL pow_sum1(LL a,LL b)

10 {

11     LL ans=0;

12     a=a%mod;

13     while(b)

14     {

15         if(b&1)

16         {

17             ans=ans+a;

18             if(ans>=mod)

19             ans=ans-mod;

20         }

21         b=b>>1;

22         a=a<<1;

23         if(a>=mod)

24         a=a-mod;

25     }

26     return ans;

27 }

28 

29 LL pow_sum2(LL n,LL m)

30 {

31     LL ans=1;

32 

33     n=n%10000;

34     while(m)

35     {

36         if(m&1)

37         {

38             ans=pow_sum1(ans,n);

39         }

40         n=pow_sum1(n,n);

41         m=m>>1;

42     }

43     return ans;

44 }

45 

46 int main()

47 {

48     LL T,n,m;

49     scanf("%lld",&T);

50     while(T--)

51     {

52         scanf("%lld%lld",&n,&m);

53         n=pow_sum2(n,m);

54         if(n<10)printf("000");

55         else if(n<100) printf("00");

56         else if(n<1000) printf("0");

57         printf("%lld
",n); 58 } 59 return 0; 60 }