航電OJ-2035人見人愛A^B
1633 ワード
人は人を見てA^Bを愛する
Problem Description A^Bの最後の3桁で表される整数を求めます.説明:A^Bの意味は「AのB次方」
Input入力データは複数のテストインスタンスを含み、各インスタンスは1行を占め、2つの正の整数AとBからなる(1<=A、B<=10000)、A=0、B=0であれば入力データの終了を示し、処理しない.
Outputテストインスタンスごとに、A^Bの最後の3桁で表される整数を出力し、各出力が1行を占めます.
Sample Input
2 3 12 6 6789 10000 0 0
Sample Output
8 984 1
同余定理のテーマ、水問題.同余定理:数学上の記法は,a≡b(mod)その意味はa mod d=b modの下に同余定理の7つの法則1)a≡a(mod d)2)a≡b(mod)→b≡a(mod)3)(a≡b(mod),b≡c(mod)→a≡x(mod),b≡c(mod))→a≡x(mod),b≡m(mod),4)a+b≡x+m(mod)5)a-b≡x-m(mod d)6)a*b≡x*m(mod)7)a≡b(mod d)ではa-bはdを除去する
では、(a*b)(mod c)=(x*y)(mod c)x=a mod c y=b mod c
そこで(a^b)mod cという形式では中間量midを設定し,初期値が1であればb次演算を行うことで答えが得られる:mid=(mid*(a mod c))mod c
実装コードは次のとおりです.
Problem Description A^Bの最後の3桁で表される整数を求めます.説明:A^Bの意味は「AのB次方」
Input入力データは複数のテストインスタンスを含み、各インスタンスは1行を占め、2つの正の整数AとBからなる(1<=A、B<=10000)、A=0、B=0であれば入力データの終了を示し、処理しない.
Outputテストインスタンスごとに、A^Bの最後の3桁で表される整数を出力し、各出力が1行を占めます.
Sample Input
2 3 12 6 6789 10000 0 0
Sample Output
8 984 1
同余定理のテーマ、水問題.同余定理:数学上の記法は,a≡b(mod)その意味はa mod d=b modの下に同余定理の7つの法則1)a≡a(mod d)2)a≡b(mod)→b≡a(mod)3)(a≡b(mod),b≡c(mod)→a≡x(mod),b≡c(mod))→a≡x(mod),b≡m(mod),4)a+b≡x+m(mod)5)a-b≡x-m(mod d)6)a*b≡x*m(mod)7)a≡b(mod d)ではa-bはdを除去する
では、(a*b)(mod c)=(x*y)(mod c)x=a mod c y=b mod c
そこで(a^b)mod cという形式では中間量midを設定し,初期値が1であればb次演算を行うことで答えが得られる:mid=(mid*(a mod c))mod c
実装コードは次のとおりです.
#include
#define MOD(i) (i) % 1000
int main(){
int a,b;
while(scanf("%d%d",&a,&b) != EOF && a | b){
int ans = 0;
int mul_mod_value = MOD(a);
while(b--) ans = MOD(ans * mul_mod_value);
printf("%d
",ans);
}
return 0;
}