ACM – UVA11029 – 快速幂,快速前幂

点击量:25

后面的三位快速幂即可,但是前面三位不好求。经过分析,每一位都有可能牵扯到前三位的值,因此无法具体的作出判断。

如果使用模方法省去后面的部分,必定会造成误差,随着省略的部分增多,误差积累势必会越来越大。(错了一组数据)

最佳的方法还是数学分析(参考了题解):
分析n,$a = log_{10}^n$,则$n = a ^ {10}$。分解a = i + d,i为正数部分,d为小数部分。那么i影响的仅仅是位数,d影响的则是具体的数字。

这样得到的值是准确的。另外对浮点数取余

fmod(double, mod)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll unsigned long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int pow_mod(int x, int k, int p)
{
    int ans = 1;
    x %= p;
    while(k)
    {
        if(k&1) ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}
int solve(int n, int k)
{
    double d = log10(n*1.0);
    int ans = (int)pow(10, 2 + fmod(k*d, 1));
    return ans;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    int n, k;
    cin >> T;
    while(T--)
    {
        scanf("%d%d", &n, &k);
        int ans2 = pow_mod(n, k, 1000);
        int ans1 = solve(n, k);
        printf("%d...%03d\n", ans1, ans2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注