人见人爱A^B
Problem Description 求A^B的最后三位数表示的整数。 说明：A^B的含义是“A的B次方” Input 输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。 Output 对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。 Sample Input 2 3 12 6 6789 10000 0 0 Sample Output 8 984 1
// #include<iostream> using namespace std; int gcd(int n,int m) { int test,t,ans; test=m; n=n%1000; ans=1; while(test){ if(test&1==1) ans=n*ans%1000; n=n*n%1000; test>>=1; } return ans; } int main() { int m,n; while(cin>>n>>m){ if(m+n==0) break; cout<<gcd(n,m)<<endl; } return 0; }
主要是二分思想，
//二分实现 #include<iostream> using namespace std; int gcd(int t){ int s=1; int ans=0; while(t){ if(t&1) ans+=s; s*=2; t>>=1; } return ans; } int main() { int m; cin>>m; cout<<gcd(m)<<endl; }