一道基础的ACM数学编程题When we were young,everyone was taught that:"If the sum of a number's each bit could be exactly divided by 3,then itself would be exactly divided by 3",so for a k-base number,if that the sum of its each bit could be e
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/26 02:38:22
一道基础的ACM数学编程题When we were young,everyone was taught that:"If the sum of a number's each bit could be exactly divided by 3,then itself would be exactly divided by 3",so for a k-base number,if that the sum of its each bit could be e
一道基础的ACM数学编程题
When we were young,everyone was taught that:"If the sum of a number's each bit could be exactly divided by 3,then itself would be exactly divided by 3",so for a k-base number,if that the sum of its each bit could be exactly divided by n can infer that the number itself would be exactly divided by n,then we called n is a "Skillful Dividing" number on k-base.To find all of the "Skillful Dividing" numbers on k-base is not easy ,but your task is just to find all of "Skillful Dividing" numbers,SD number for short.
输入要求
Input consists of multiple test case .Each case will include a k,input will end with EOF.
输出要求
For each test case,print the amount of SD numbers on k-base
假如输入
10
4
应当输出
3
2
提示
1,3,9 are SD numbers on 10-base.
每一位相加能被3整除的数这个数可以被3整除,对于一个有k位的数,每一位相加能被n整除,那么这个数就能被n整除,n叫做Skillful dividing number on k-base（k位数被有效划分的数,缩写SD）,n是短整型数,要求输入多测试数据,每个数据是k,输入EOF为止,输出SD数的个数
思路正确者加分
一道基础的ACM数学编程题When we were young,everyone was taught that:"If the sum of a number's each bit could be exactly divided by 3,then itself would be exactly divided by 3",so for a k-base number,if that the sum of its each bit could be e
纠结下,k-base 这是指k进制,不是指k位的数.
这个题的意思是,找出n的个数,n的意思是,能被一个多位数整除,同时该每个数相加后也能被整除.
下面说下为什么这个多位数(m位)有这种性质.
比如这个多位数是data. 在k进制下有,
data=(ai)*k^(m-i-1) (i=0...m-1 ; ai表示data的每一位）
如果存在一个p,使得 k mod p = 1 则 对于所有的 k^(i) mod p =1
那个 data mod p = ai (i=0,m-1) .
也就是 p就是我们所要找的, 而寻找的方法 就是 for(i=1;i 10^0 mod 3=1 .. 10^2 mod 3= 1 （同余的性质 )
所以 123 mod 3 = (1+ 2 +3 ) mod 3
如果右边相加能被3整除,即左边为0 ,那右边也为0 .