【题目来源】
洛谷：[P10262 GESP样题 六级] 亲朋数 - 洛谷
【题目描述】
给定一串长度为 \(L\)、由数字 \(0\sim 9\) 组成的数字串 \(S\)。容易知道，它的连续子串共有 \(\frac{L(L + 1)}2\) 个。如果某个子串对应的数（允许有前导零）是 \(p\) 的倍数，则称该子串为数字串 \(S\) 对于 \(p\) 的亲朋数。
例如，数字串 \(S\) 为“ \(12342\) ”、\(p\) 为 \(2\)，则在 \(15\) 个连续子串中，亲朋数有“ \(12\) ”、“ \(1234\) ”、“ \(12342\) ”、“ \(2\) ”、“ \(234\) ”、“ \(2342\) ”、“ \(34\) ”、“ \(342\) ”、“ \(4\) ”、“ \(42\) ”、“ \(2\) ”共 \(11\) 个。注意其中“ \(2\) ”出现了 \(2\) 次，但由于其在 \(S\) 中的位置不同，记为不同的亲朋数。
现在，告诉你数字串 \(S\) 和正整数 \(p\) ，你能计算出有多少个亲朋数吗？
【输入】
输入的第一行，包含一个正整数 \(p\)。约定 \(2 \leq p \leq 128\)。
输入的第二行，包含一个长为 \(L\) 的数字串 \(S\)。约定 \(1 \leq L \leq 10^6\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
2
102
【输出样例】
5
【算法标签】
《洛谷 P10262 亲朋数》 #动态规划DP# #GESP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long // 将int重新定义为long long类型
const int N = 150; // 定义常量N，最大模数p的范围
int p, f[N], g[N], ans; // p: 模数, f/g: 动态规划数组, ans: 结果计数
string s; // 输入的数字字符串signed main() // 因为使用了#define int long long, 所以用signed main
{cin >> p >> s; // 输入模数p和数字字符串sint len = s.size(); // 获取字符串长度s = " " + s; // 在字符串前添加空格，使索引从1开始for (int i = 1; i <= len; i++) // 遍历字符串的每个字符{memset(g, 0, sizeof(g)); // 清空g数组，用于存储当前状态for (int j = 0; j < p; j++) // 遍历所有可能的余数{// 状态转移: 从之前的余数j转移到新的余数t// 新的余数t = (j*10 + 当前数字) % pint t = (j * 10 + s[i] - '0') % p; // 计算新余数g[t] += f[j]; // 从f[j]状态转移到g[t]}// 特殊情况: 当前数字单独构成子串g[(s[i] - '0') % p]++; // 当前数字单独组成的数字对p取模ans += g[0]; // 统计余数为0的子串数量memcpy(f, g, sizeof(g)); // 将g数组复制到f数组，用于下一轮迭代}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
2
102
5