小C的倍数问题
思路
首先先要知道 \(3\) 在十进制中为什么是可以的：
设三位数 \(\overline{abc}\) 能被 \(3\) 整除：
那么：
\(\because100a + 10b+c \equiv0\pmod{3}\)
\(\therefore99a+9b+0c+(a+b+c)\equiv0\pmod{3}\)
\(\because99a+9b+0c\equiv3(33a+3b+0c)\equiv0\pmod{3}\)
\(\therefore(a+b+c)\equiv0\pmod{3}\)
那么我们可得知进制为 \(p\), 数为 \(\overline{abc}\) 的式子：
\(p^2a+pb+c\)
\((p^2-1)a+(p-1)b+0+(a+b+c)\)
那么我们只要证明 \((p^2-1)a+(p-1)b+0\) 能被 \(x\) 整除，那么 \(a+b+c\) 就能被整除，也就符合要求。
考虑 \((p^2-1)a+(p-1)b+0\)：
可以将其转换为：
\((p^2-1^2)a+(p-1)b+0\)
\((p-1)(p^1+p^0)a+(p-1)b+0\)
\((p-1)((p^1+p^0)a+b+0)\)
那么就只要判断 \((p-1)\) 是否可以被 \(x\) 整除，如果成立，那么：
\(\because p-1\equiv0\pmod{p}\)
\(\therefore p^2-1\equiv0\pmod{p}\)
\(\therefore p^3-1\equiv0\pmod{p}\)
以此类推……
所以我们知道如果 \((p - 1)\) 能被 \(x\) 整除，那么 \(((p^1+p^0)a+b+0)\) 也一定能被 \(x\) 整除，所以只用考虑 \((p - 1)\) 不必考虑 \(((p^1+p^0)a+b+0)\)，那么有多少个 \(x\) 能整除 \((p - 1)\) 呢？ 显然是因数个数，所以计算 \((p - 1)\) 因数个数即可。
code
点击查看代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 1e3 + 10;
int t, p, cnt;
int main () {
ios::sync_with_stdio(0), cin.tie(0);
for (cin >> t; t; t--) {
cin >> p, cnt = 0;
for (int i = 1; i * i <= p - 1; i++) {
if ((p - 1) % i == 0) {
cnt += 2;
((p - 1) / i == i) && (cnt--);
}
}
cout << cnt << endl;
}
return 0;
}