HDU - 5690分治 + 快速幂思想

题意：

判断数位长度为m且每一位上的数字都是x的数模k的结果是否等于c。

思路：

也可以算是一种分治吧，把大的整数按数位折半考虑，类似于快速幂的处理方式，如果是偶数，前一半和后一半的结果相同，不需要重复处理，如果是奇数，合并的时候加上中间的x即可。

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll pow_mod(ll a, ll n, ll mod) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } ll dfs(ll x, ll n, ll mod) { if (n == 1) return x; ll mid = n / 2, res; ll tmp = dfs(x, mid, mod); if (n & 1) res = (tmp * 10 + x) % mod * pow_mod(10, mid, mod) % mod; else res = (tmp * pow_mod(10, mid, mod)) % mod; return (res + tmp) % mod; } int main() { int T, cs = 0; scanf("%d", &T); while (T--) { ll x, m, k, c; scanf("%I64d%I64d%I64d%I64d", &x, &m, &k, &c); printf("Case #%d:\n", ++cs); if (dfs(x, m, k) == c) puts("Yes"); else puts("No"); } return 0; }