数论常用内容——数根

对于数根可能接触的不多，但是我觉得这里还是应该做一下简单的总结和介绍

数根

数根(又称数字根Digital root)是自然数的一种性质，每个自然数都有一个数根。

数根是将一正整数的各个位数相加(即横向相加)，若加完后的值大于等于10的话，则继续将各位数进行横向相加直到其值小于十为止，最后得到的数字就是该数的数根

数根的性质

root(a+b)=root(root(a)+root(b))root(a*b)=root(root(a)*root(b))root(a)=root(root(a/10)+a%10)

几种常用数根计算的代码实现

• n的数根（模拟）

int root(int n){while(n>9){n=n%10+n/10;}return n;
}

• n的数根（找规律）

int _root(int n){return n?(n+8)%9+1:0;
}// 公式
root(x) = (x-1)%9+1

1. 公式推导过程

• n的数根（大数）

int __root(char *p){int n=0;for(int i=0;p[i];i++){n+=p[i]-'0';}return n?(n+8)%9+1:0;
}

• n^n的数根（找规律）

int digitalRoot(int n){int tree[19]={9,1,4,9,4,2,9,7,1,9,1,5,9,4,7,9,7,8};return tree[n%18];
}

• a^b的数根（模拟）

int _digitalRoot(int a,int b){a=root(a);int ans=1;while(b--)ans=root(ans*a);return ans;
}

• a^b的数根（二进制法）

int __digitalRoot(int a,int b){a=root(a);int t=a,ans=1;while(b){if(b&1)ans=root(ans*t);b>>1;t=root(t*t);}return ans;
}