|
发表于 2022-1-8 15:55:17
|
显示全部楼层
本帖最后由 guosl 于 2022-1-8 16:34 编辑
本题难点在数据的范围,由于求的是最后10位,那么在计算中至少要保留10,但两个10位数的乘,就可能是20位超出了long long的数据范围,所以一般计算机语言中数据类型没有一个可以处理这样长的整数。为此要么借用扩展库要么自己添加自己的扩展数据类型来处理本题。下面我采用两种方式来解决这题。
第一种方式:借用扩展库mpir,具体参考网站:http://www.mpir.org/
- /*
- 答案:9110846700
- 耗时:0.0007467秒
- */
- #include <iostream>
- #include <mpir.h>
- using namespace std;
- int main(void)
- {
- long long nSum = 0;
- mpz_t rop, base, mod;
- mpz_inits(rop, base, mod, 0);
- mpz_set_ui(mod, 10000000000ll);
- for (int i = 1; i <= 1000; ++i)
- {
- mpz_set_ui(base, i);
- mpz_powm_ui(rop, base, i, mod);
- nSum += mpz_get_ui(rop);
- }
- mpz_clears(rop, base, mod, 0);
- nSum %= 10000000000ll;
- cout << nSum << endl;
- return 0;
- }
复制代码
下面是自定义数据类型stBigInt来解决的
- /*
- 答案:9110846700
- 耗时:0.000315秒
- */
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- struct stBigInt
- {
- int a[3];//每个a保存4位10进制数,故整个新类型可以保存12位10进制数
- //三个构造函数
- stBigInt(void)
- {
- memset(a, 0, sizeof(a));
- }
- stBigInt(short n)
- {
- memset(a, 0, sizeof(a));
- a[0] = n;
- }
- stBigInt(const stBigInt& b)
- {
- memcpy(a, b.a, sizeof(a));
- }
- //运算符重载
- const stBigInt& operator=(const stBigInt& b)//赋值
- {
- memcpy(a, b.a, sizeof(a));
- return *this;
- }
- stBigInt operator+(const stBigInt& b) const //加
- {
- int d = 0;//进位
- stBigInt x;
- for (int i = 0; i < 3; ++i)
- {
- d += a[i] + b.a[i];
- x.a[i] = d % 10000;
- d /= 10000;
- }
- x.a[2] %= 100;//保留10位
- return x;
- }
- stBigInt operator*(const stBigInt& b) const //乘
- {
- stBigInt x;
- for (int i = 0; i < 3; ++i)
- {
- for (int j = 0; j < 3; ++j)
- {
- if (i + j < 3)
- x.a[i + j] += a[i] * b.a[j];
- }
- }
- int d = 0;
- for (int i = 0; i < 3; ++i)
- {
- d += x.a[i];
- x.a[i] = d % 10000;
- d /= 10000;
- }
- x.a[2] %= 100;//保留10位
- return x;
- }
- //函数
- stBigInt qpow(int n)//快速幂
- {
- stBigInt x(1);
- if (n == 0)
- return x;
- if (n == 1)
- return *this;
- if ((n & 1) == 0)
- {
- x = qpow(n >> 1);
- x = x * x;
- }
- else
- {
- x = qpow(n - 1);
- x = x * (*this);
- }
- return x;
- }
- };
- int main(void)
- {
- stBigInt nSum;
- for (int i = 1; i <= 1000; ++i)
- {
- stBigInt x(i);
- x = x.qpow(i);
- nSum = nSum + x;
- }
- printf("%d", nSum.a[2]);
- printf("%04d", nSum.a[1]);
- printf("%04d\n", nSum.a[0]);
- return 0;
- }
复制代码 |
|