1、HDU1013 求一个 positive integer 的 digital root,即不停的求数位和,直到数位和为一位数即为数根。
一开始,以为 integer 嘛,指整型就行吧 = =(too young),后来大数自然用字符串解决,然后 get 到一个新数论点九余数定理;
https://en.wikipedia.org/wiki/Digital_root
即:一个数的数根等于它模 9 的余数。(=》几个数之积的九余数 = 每个数的九余数之积的九余数。) 2、HDU1163,2035 求 n^n 的数根,即九余数定理加快速幂取模。
快速幂:有递归,非递归,位运算实现等方式。主要思想就是 x 的 m 次方,可拆分为奇数时为 x*(x^m)^2,偶数时为(x^m)^2;利用位运算就是利用 n 的二进制的位权值,如 x^11 即 11 的二进制表示为 1011,x^11=x*2^0+x*2^1+x*2^3;由原来需要计算的 11 步,简化为了三步。HDU2035 就是最基本的快速幂取模,取模是因为指数函数的增长速度太快,往往会超出 long long 的数据范围。
- //HDU2035快速幂取模
- #include <cstdio>
- #include <iostream>
- int pow(int x,int n)
- {
- int base=x,ans=1;
- while(n)
- {
- if(n&1) ans=(ans*base)%1000;
- base=(base*base)%1000;
- n>>=1;//位运算实现
- }
- return ans;
- }
- using namespace std;
- int main()
- {
- int a,b;
- while(cin >> a >> b,a||b)
- {
- cout << pow(a,b) << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2437572.html