HDU6108《小C的倍数问题》

真·小学数学

Problem Description

根据小学数学的知识,我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之,如果一个数每一位加起来是3的倍数,则这个数肯定是3的倍数。

现在给定进制P,求有多少个B满足P进制下,一个正整数是B的倍数的充分必要条件是每一位加起来的和是B的倍数。

Input

第一行一个正整数T表示数据组数(1<=T<=20)。

接下来T行,每行一个正整数P(2 < P < 1e9),表示一组询问。

Output

对于每组数据输出一行,每一行一个数表示答案。

Sample Input

1
2
1
10

Sample Output

1
3

解析

小 学 数 学


考虑$p$进制表示的实质是
$x = a1p^n+a_2p^{(n - 1)} + a_3p^{(n - 2)} + \dots + a{n+1}$
稍微变形一下

然后注意到$p^n - 1=(p - 1)(p^{n - 1} + p^{n - 2} + \dots + 1)$
把它代入进去

发现前面几项都有一个 $p - 1$
那么,当且仅当$\sum_{i = 1}^{n + 1}a_i$,即 x 各位数字之和 $\equiv 0(\bmod (p - 1))$ 时,$x \equiv 0 (\bmod (p - 1))$

one more thing
对于任意的自然数$a,p$,如果 $a \mod p = 0$,那么有$a \mod x = 0(x \mid p)$

所以这题的思路已经很明显了,求的就是$p - 1$的因子个数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// Created by HandwerSTD on 2019/10/13.
//

#include <iostream>
#include <cstdio>
#include <cmath>

int T;

int main() {
scanf("%d", &T);
while (T --> 0) {
int fx = 0, ans = 0;
scanf("%d", &fx); --fx;
for (int i = 1, fs = sqrt(fx); i <= fs; ++i) {
if (fx % i != 0) continue;
++ans; if ((fx / i) != i) ++ans;
}
printf("%d\n", ans);
}
return 0;
}