使用数论知识消除模拟

题目

杭电Problem-1013 Digital Roots

题目简述

一个数各进制位之和是一位数那么这个和就是这个数的根,如果各进制之和不是一位数,则这个和的根就是这个数的根。求一些给定数的根。

解题思路

这是我的解题思路,也是一般的模拟方法,其实这道题利用数论可以无限简化,等说完一般的,我再贴出某大神的数论式解法。以字符串读入(数据范围很大),计算出各进制位之和(各进制位之和用long int储存就可以了,因为一个1000位的数字各进制数之和最大也就9000),如果是个位数就输出,如果不是就再求各进制位之和来求根。

我的代码

#include <stdio.h>
#include <string.h>

long ReX(char n[])
{

long x,i,v;
while(1)
{
x=0,i=0;
while( n[i]!='\0' )
x += n[i++]-'0';
if(x>=0&&x<=9) return x;
v=sprintf(n,"%ld",x);
n[v]= '\0';
}
}
int main(void)
{

char t[10000]; /*这里我一开始只开了200,总是不能AC,找了很久,才发现数组开小了,鄙视下题目不给数据范围*/
while(gets(t),t[0]!='0')
printf("%ld\n",ReX(t));
return 0;
}

某大神的极简代码

#include <stdio.h>
#include <string.h>

int main(void)
{

int a,c;
for(;scanf("%1d",&a),a>0;printf("%d\n",--a%9u+1))
while((c=getchar())-48u<10)
a+=c-48;
return 0;
}

我刚开始看到这段代码都震撼了(感叹!原来还能这样)。

  1. 一位数模9是它本身(9除外);整十数模9是它十位的数字(90除外);整百数摸9是它百位的数字(900除外)……
  2. 对于一个一般的数,可以分拆成几个10的幂的和;一般的数模9的结果,实质就是题目所描述的”数字根”(9的倍数除外)。
  3. 反复提到9的倍数除外,那这个除外的结果是什么?想一下就清楚.所以楼主先–a再%9最后+1就是在处理这种情况。
  4. 数字后面跟u后缀代表无符号整数,至于9啊48啊还要加这个,那是楼主在炫耀他的代码能力,大家可无视之。
  5. 最后提醒 48 == ‘0’

第四点是错误的,这里的U标识是必要的,因为读到回车(10)时,10-48<10会继续循环,而加上U变为10-48U时运算结果是一个非常大的数因而跳出循环。