cug 1126 快速模幂

2019-04-14 16:27发布

站内文章 / 模拟电子
15984 0 960
题目大意：求n^m的最后一位数 解法一：找规律 因为最后一位最多有十个，所以必然会出现循环，直接找规律即可。（比快速模幂效率高一点点） #include #include #include #include #include #include #include #include using namespace std; int main() { long long m , n , ncase; cin >> ncase; int A[20]; while(ncase -- ) { cin >> m >> n; long long tt = m; while(tt > 10) { tt %= 10; } if( tt == 0) { cout << "0" << endl; continue; } memset(A , 0 , sizeof(A)); long long t = 1; int k = 1; int pos = -1; for(int i = 1 ; i <= n ; i ++ ) { t *= m; while(t > 10) { t %= 10; } for(int j = 0 ; j < k ; j ++ ) { if(A[j] == t) { pos = j; break; } } if(pos == -1) A[k++] = t; else break; } if(pos != -1) { int res = k - pos; res = (n - (pos - 1)) % (res); if(res == 0) cout << A[k - 1] << endl; else cout << A[pos + res - 1] << endl; } else cout << t << endl; } return 0 ; }解法二：快速模幂 #include #include using namespace std; int pow_mod(int a,int n,int m) { if(n==0)return 1; int x=pow_mod(a,n/2,m); long long ans=(long long)x*x%m; if(n%2==1)ans=ans*a%m; return (int)ans; } int main() { long long a,b; int t; cin>>t; while(t--) { scanf("%I64d%I64d",&a,&b); cout<



热门文章