uva 11029 - Leading and Trailing(快速幂）

 

题目大意：给出一个n和k求n^k的前三位数和后三位数。

 

解题思路：后三为数可以用分治的方法（快速幂）去做，可是前三位数就比较麻烦了，看了别人的题解.

n^k = 10 ^ (k * log10(n)),所以可以将多余的位数移到小数点后面然后舍弃掉，只保留前三位，pow(10, 2 + fmod(k * log10(n), 1)).

 

 

 

#include <stdio.h>  
#include <math.h>  
int n, k;  
  
long long pow_mod(long long a, long long c) {  
    if (c == 1) return a % 1000;  
    long long ans = pow_mod(a, c / 2);  
    ans = (ans * ans) % 1000;  
    return c % 2 ? (ans * a) % 1000 : ans;  
}  
  
void solve() {  
    int l = (int) pow(10, 2 + fmod(k * log10(n), 1));  
    int r = pow_mod(n, k);  
    printf("%d...%03d\n", l, r);  
}  
  
int main () {  
    int cas;  
    scanf("%d", &cas);  
    while (cas--) {  
        scanf("%d%d", &n, &k);  
        solve();  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,