「NOI2016」循环之美

题意

求解 $1\le x\le n,1\le y\le m$ 中满足在 $k$ 进制下 $\frac{x}{y}$ 是有限循环小数的个数

题解

很好然后我一开始在计算器上敲了半个小时然后由于眼瞎并且归纳能力差并没有发现规律

设 $\frac{x}{y}$ 的循环节长度为 $l$，则有
$$\begin{array}{rl}\frac{x{k}^l}{y}-\lfloor \frac{x{k}^l}{y}\rfloor & =\frac{x}{y}-\lfloor \frac{x}{y}\rfloor \\ x{k}^l-\lfloor \frac{x{k}^l}{y}\rfloor y& =x-\lfloor \frac{x}{y}\rfloor y\\ x{k}^l& \equiv x(\mathrm{mod}y)\\ k& \equiv 1(\mathrm{mod}y)\end{array}$$
也就是说只要满足 $y\mathrm{\perp }k$ 即可满足题意，故可将问题化为
$$\begin{array}{rl}Ans& =\sum _{i=1}^n\sum _{j=1}^m[(i,j)=1][(j,k)=1]\\ & =\sum _{j=1}^m[(j,k)=1]\sum _{d|j}\mu (d)\lfloor \frac{n}{d}\rfloor \\ & =\sum _{d=1}^n\mu (d)\lfloor \frac{n}{d}\rfloor \sum _{d|j}[(j,k)=1]\\ & \mathrm{将}j\mathrm{除}\mathrm{以}d,\mathrm{此}\mathrm{时}\mathrm{若}\mathrm{后}\mathrm{半}\mathrm{部}\mathrm{分}\mathrm{的}\sum \mathrm{要}\mathrm{有}\mathrm{贡}\mathrm{献}\mathrm{则}\mathrm{需}\mathrm{满}\mathrm{足}d\mathrm{\perp }k\\ & =\sum _{d=1}^n[(d,k)=1]\mu (d)\lfloor \frac{n}{d}\rfloor (\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[(j,k)=1])\end{array}$$
于是接下来变为处理
$$\begin{gathered} f_1(n,k)=\sum _{d=1}^n[(d,k)=1]\mu (d) \\ {f}_2(n)=\sum _{d=1}^n[(d,k)=1] \end{gathered}$$
先说 $f_2(n)$，较好处理，即考虑长度为 $k$ 的区间将 $n$ 分段，其中除了最后多出来的那一段其余的段得到的贡献是相同的，即 $\phi (k)$，故
$$f_2(n)=\lfloor \frac{n}{k}\rfloor \phi (k)+f_2(n\mathrm{\%}k)$$
那么对于 $f_1(n,k)$，容易变换得
$$f_1(n,k)=\sum _{d|k}^n\mu (d)\sum _{l=1}^{\lfloor \frac{n}{d}\rfloor }\mu (ld)$$
然后我就不会了，看了下题解，可以发现若 $\mu (ld)$ 有贡献，则需满足 $l\mathrm{\perp }d$，此时有 $\mu (ld)=\mu (l)\mu (d)$，故
$$\begin{array}{rl}{f}_1(n,k)& =\sum _{d|k}\mu (d)\sum _{l=1}^{\lfloor \frac{n}{d}\rfloor }\mu (l)\mu (d)[(d,l)=1]\\ & =\sum _{d|k}{\mu }^2(d)\sum _{l=1}^{\lfloor \frac{n}{d}\rfloor }\mu (l)[(d,l)=1]\\ & =\sum _{d|k}{\mu }^2(d)f_1(\lfloor \frac{n}{d}\rfloor ,d)\end{array}$$
很好我还是第一次写到莫反带递归的

注意边界条件 $n=0$ 与 $k=1$，对于 $n=0$ 返回 $0$ 即可，对于 $k=1$，$f_1(n,1)$ 即为 $\sum _{d=1}^n\mu (d)$，杜教筛一下即可

最后再整除分块一次求总答案就好了

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <tr1/unordered_map>
#include <map>

using namespace std;

typedef long long LL;

const int MAXM = 1e06 + 10;
const int MAXK = 2000 + 10;

const int MAX = 1e06;

int N, M, K;

int prime[MAXM / 10]= {0};
bool visit[MAXM]= {false};
int pcnt = 0;
int mu[MAXM]= {0}, sumu[MAXM]= {0};
void linear_sieve () {
	sumu[1] = mu[1] = 1;
	for (int i = 2; i <= MAX; i ++) {
		if (! visit[i]) {
			prime[++ pcnt] = i;
			mu[i] = - 1;
		}
		for (int j = 1; j <= pcnt && i * prime[j] <= MAX; j ++) {
			visit[i * prime[j]] = true;
			if (! (i % prime[j])) break;
			mu[i * prime[j]] = - mu[i];
		}
		sumu[i] = sumu[i - 1] + mu[i];
	}
}

tr1::unordered_map<int, int> mapmu;
int mu_sieve (int n) {
	if (n <= MAX) return sumu[n];
	if (mapmu[n]) return mapmu[n];
	int total = 1;
	for (int l = 2, r; l <= n; l = r + 1) {
		r = n / (n / l);
		total -= (r - l + 1) * mu_sieve (n / l);
	}
	return mapmu[n] = total;
}
LL f[MAXK]= {0};
LL sumr[MAXM]= {0}; // sigma ([(j, k) = 1])
int GCD (int a, int b) {
	return ! b ? a : GCD (b, a % b);
}
void r_sieve () {
	for (int i = 1; i <= K; i ++)
		f[i] = f[i - 1] + (GCD (i, K) == 1);
}
int rval (int n) {
	return (n / K) * f[K] + f[n % K];
}

map<pair<int, int>, int> mapl;
LL l_solve (int n, int k) { // S(n, K)
	if (! n) return 0;
	pair<int, int> ret = make_pair (n, k);
	if (mapl[ret]) return mapl[ret];
	if (k == 1) return mu_sieve (n);
	LL total = 0;
	for (int i = 1; i * i <= k; i ++)
		if (! (k % i)) {
			if (mu[i]) total += l_solve (n / i, i);
			if (i * i != k && mu[k / i])
				total += l_solve (n / (k / i), k / i);
		}
	return mapl[ret] = total;
}

int main () {
	linear_sieve ();
	scanf ("%d%d%d", & N, & M, & K);
	r_sieve ();
	LL ans = 0, pre = 0;
	for (int l = 1, r; l <= min (N, M); l = r + 1) {
		r = min (N / (N / l), M / (M / l));
		LL pl = l_solve (r, K);
		ans += 1ll * (pl - pre) * (N / l) * rval (M / l);
		pre = pl;
	}
	cout << ans << endl;

	return 0;
}

/*
2 6 10
*/

/*
99 7689 100
ans: 257777
*/

方法二

我没有写这种方法，但是这种真的很简单的说
$$\begin{array}{rl}f(n,m,k)& =\sum _{i=1}^n\sum _{j=1}^m[(i,j)=1][(j,k)=1]\\ & =\sum _{i=1}^n\sum _{j=1}^m[(i,j)=1]\sum _{d|j,d|k}\mu (d)\\ & =\sum _{d|k}\mu (d)\sum _{i=1}^n\sum _{d|j}^m[(i,j)=1]\\ & =\sum _{d|k}\mu (d)\sum _{i=1}^n\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[(i,jd)=1]\\ & =\sum _{d|k}\mu (d)\sum _{i=1}^n\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[(i,j)=1][(i,d)=1]\\ & =\sum _{d|k}\mu (d)f(\lfloor \frac{m}{d}\rfloor ,n,d)\end{array}$$
边界 $n=0$ 或者 $m=0$ 返回 $0$，$k=1$ 返回 $\sum _{i=1}^n\sum _{j=1}^m[(i,j)=1]=\sum _{i=1}^{min(n,m)}\mu (d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor$ 即可

不过说实话这个虽然简单但是至少对于我不大容易想到，毕竟我会先拆 $[(i,j)=1]$ 部分，因为总感觉 $[(j,k)=1]$ 会多出一个 $d|k$ 的限制条件

但是这个解法是真的厉害