LightOJ - 1282 Leading and Trailing （数论）

题意：求n^k的前三位和后三位。

分析：

1、后三位快速幂取模，注意不足三位补前导零。

补前导零：假如n^k为1234005，快速幂取模后，得到的数是5，因此输出要补前导零。

2、前三位：

令n=10^a，则n^k=10^ak=10^x+y，x为ak的整数部分，y为ak的小数部分。

eg：n=19,k=4,则n^k=130321,

a=log₁₀(n)=1.2787536009528289615363334757569

ak=5.1150144038113158461453339030277,

因此，x=5，y=0.1150144038113158461453339030277，

10^y=1.3032099999999999999999999999999，因此要获得前三位只需要10^y*100下取整即可。

3、注意：

log(double x)---底数为e

log10(double x)---底数为10

log2(double x)---底数为2

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int POW_MOD(int n, int k, int MOD){

    if(k == 0) return 1 % MOD;

    int tmp = POW_MOD(n, k >> 1, MOD);

    long long ans = (tmp * tmp) % MOD;

    if(k & 1) (ans *= (n % MOD)) %= MOD;

    return ans;

}

int main(){

    int T;

    scanf("%d", &T);

    int kase = 0;

    while(T--){

        int n, k;

        scanf("%d%d", &n, &k);

        int x = (int)(pow(10.0, fmod(log10(n * 1.0) * k, (int)(log10(n * 1.0) * k))) * 100);

        int y = POW_MOD(n, k, 1000);

        printf("Case %d: %d %03d\n", ++kase, x, y);

    }

    return 0;

}

巴特西

LightOJ - 1282 Leading and Trailing （数论）

最新文章

热门文章