HDU6108《小C的倍数问题》

十月 13, 2019 1667

真·小学数学

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 = a_1p^n+a_2p^{(n - 1)} + a_3p^{(n - 2)} + \dots + a_{n+1}
稍微变形一下
MATHJAX-SSR-711
然后注意到 p^n - 1=(p - 1)(p^{n - 1} + p^{n - 2} + \dots + 1)
把它代入进去
MATHJAX-SSR-712
发现前面几项都有一个 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
24
//
// 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;
}