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 }