Description

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 $k$ 进制下,一个数的小数部分是纯循环的,那么它就是美的。

现在,牛牛想知道:对于已知的十进制数 $n$ 和 $m$,在 kk 进制下,有多少个数值上互不相等的纯循环小数,可以用分数 $xy$ 表示,其中 $1≤x≤n,1≤y≤m$,且 $x,y$ 是整数。

一个数是纯循环的,当且仅当其可以写成以下形式:

其中,a 是一个整数,$p≥1$;对于 $1≤i≤p$,$c_i$ 是 $k$ 进制下的一位数字。

例如,在十进制下,$0.45454545……$ 是纯循环的,它可以用 $\frac{5}{11}$、$\frac{10}{22}$ 等分数表示;在十进制下,$0.1666666……$ 则不是纯循环的,它可以用 $\frac{1}{6}$ 等分数表示。需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环;而一个小数部分非 $0$ 的有限小数不是纯循环的。

Input

只有一行,包含三个十进制数$n,m,k$,意义如题所述,保证 $1≤n≤10^9,1≤m≤10^9,2≤k≤2000$

Output

一行一个整数,表示满足条件的美的数的个数。

Solution

首先考虑如何判断$\frac{x}{y},(x, y) = 1$是否是纯循环的,即存在$l > 0$, 使

即$(y, k) = 1$,所以答案就是

按$\lfloor \frac{m}{d} \rfloor$与$\lfloor \frac{n}{d} \rfloor$分组,于是我们需要计算的是

注意到$k$的质因子最多有4个,不妨设$F(i, r)$为仅考虑$k$的前$i$个质因子时的$F(r)$值,$G(i, r)$同理,设$k = \prod p_i^{c_i}$,于是可以得到递推式:

注意此处由于当$d$没有重复质因子时$\mu(d)$才会有取值,所以转移时减去的是$\mu(p_i) F(i, …)$

G的边界条件很容易计算,而对于F我们实际上要计算$\mu$的前缀和:

这样就可以杜教筛了,我们预处理出$n^{\frac{2}{3}}$以内的$\mu$.对于更大的范围,由于上式中$\frac{r}{i}$只有$O(\sqrt {r})$种取值,从小到大每个需要$O(\sqrt{r})$的时间计算(此时可以保证$M(\lfloor \frac{r}{i} \rfloor)$已在之前计算过了)

总时间复杂度为$O(\omega(k) \sqrt{n} + n^{\frac{2}{3}})$

Source

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 2001000;

int Maxn, len;

bool vis[N];
int Prime[N], miu[N], cprm;

void init(){
	miu[1] = 1;
	For(i, 2, Maxn){
		if(!vis[i]) Prime[++cprm] = i, miu[i] = -1;
		for(int j = 1; j <= cprm && 1LL * i * Prime[j] <= Maxn; j++){
			int v = i * Prime[j];
			vis[v] = true;
			if(i % Prime[j]) miu[v] = -miu[i];
			else{
				miu[v] = 0;
				break;
			}
		}
	}
	For(i, 2, Maxn) miu[i] += miu[i - 1];
}

int n, m, k;

int R[N], Rt[N], rn, rtn;
int S[5][N], T[5][N];

int fac[5], cn;

int main(){
	scanf("%d%d%d", &n, &m, &k);
	len = max(n, m);
	Maxn = max(2 * int(pow(len, 2.0 / 3.0) + 1), k);
	init();
	for(int i = len; i; i = max(n / (n / i + 1), m / (m / i + 1))) R[++rn] = i;
	reverse(R + 1, R + rn + 1);
	For(i, 1, rn){
		if(R[i] <= Maxn) S[0][i] = miu[R[i]];
		else{
			S[0][i] = 1;
			for(int r = len, l, j = 0; r > 1; r = l){
				l = R[i] / (R[i] / r + 1);
				while(R[j] < R[i] / r) ++j;
				S[0][i] -= (r - l) * S[0][j];
			}
		}
	}
	for(int i = 1; Prime[i] <= k && i <= cprm; i++)
		if(k % Prime[i] == 0) fac[++cn] = Prime[i]; 
	for(int i = m; i; i = m / (m / i + 1)) Rt[++rtn] = m / i, T[0][rtn] = m / i;
	For(i, 1, cn){
		for(int j = 1, u = 0; j <= rn; j++){
			while(R[u] < R[j] / fac[i]) ++u;
			S[i][j] = S[i - 1][j] + S[i][u];
		}
		for(int j = 1, u = 0; j <= rtn; j++){
			while(Rt[u] < Rt[j] / fac[i]) ++u;
			T[i][j] = T[i - 1][j] - T[i - 1][u];
		}
	}
	long long Ans = 0;
	for(int i = 1, j = rtn; i <= rn; i++){
		while(j && m / R[i] < Rt[j]) j--;
		Ans += 1LL * (S[cn][i] - S[cn][i - 1]) * (n / R[i]) * T[cn][j];
	}
	printf("%lld\n", Ans);
	return 0;
}