题目链接

题意分析

我们考虑一下 对于一个最简分数\(\frac{x}{y}\) 在\(k\)进制下可以表示为纯循环小数

设其循环节长度为\(l\) 同时令\([x]\)表示x的小数部分

那么

\[[\frac{x}{y}]=[\frac{xk^l}{y}] \]

也就是

\[\frac{x}{y}-\lfloor\frac{x}{y}\rfloor=\frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor \]

\[x-\lfloor\frac{x}{y}\rfloor y=xk^l-\lfloor\frac{xk^l}{y}\rfloor y \]

也就是

\[x≡xk^l(mod\ \ y) \]

由于

\(ax≡bx(mod\ c)\)且\(x⊥c\) 则\(a≡b(mod\ c)\)
\(x\),\(y\)是最简分数 所以\(x⊥y\)

所以

\[k^l≡1(mod\ \ y) \]

现在 我们可以得到\(k^l⊥y\) 要证明\(k⊥y\)
反证法:如果\(k⊥y\)不成立的话 那么\(k,y\)必然存在公共的质因子 那么\(k^l⊥y\)也必然存在公共的质因子 这与\(k^l⊥y\)矛盾
所以\(k⊥y\)

可得$$k≡1(mod\ \ y)$$

所以\(x,y\)以及\(y,k\)均互质

\[f(n,m,k)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1][gcd(j,k)=1]\\=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]\sum_{d|i,d|k}μ(d)\\=\sum_{d|k}μ(d)\sum_{i=1}^n\sum_{j=1}^m[d|j][gcd(i,j)=1]\\=\sum_{d|k}μ(d)\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,jd)=1]\\=\sum_{d|k}μ(d)\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1][gcd(i,d)=1]\\=\sum_{d|k}μ(d)\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{j=1}^n[gcd(i,j)=1][gcd(j,d)=1]\\=\sum_{d|k}μ(d)f(\lfloor\frac{m}{d}\rfloor,n,d) \]

从而因此不断递归下去

\(n=0\)或者\(m=0\)时

\[f(n,m,k)=0 \]

\(k=1\)时

\[f(n,m,k)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]=\sum_{d=1}^{min(n,m)}μ(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \]

上式使用杜教筛计算

同时为了节省时间 我们还需要记忆化

CODE:

#include
#define M 10000080
#define N 3010
using namespace std;
struct Node
{
	int xx,yy,zz;
	friend bool operator <(const Node &A,const Node B)
	{return A.zz==B.zz ? (A.yy==B.yy ? A.xx dell[N];
map MUL;//用于记忆化答案
map vis;
void pre()
{
	mul[1]=1;
	for(int i=2;i<=10000000;++i)
	{
		if(!mark[i]) {prime[++tot]=i;mul[i]=-1;}
		for(int j=1;j<=tot&&prime[j]*i<=10000000;++j)
		{
			mark[prime[j]*i]=1;
			if(i%prime[j]==0)
			{
				mul[prime[j]*i]=0;
				break;
			}
			else mul[prime[j]*i]=-mul[i];
		}
	}
	for(int i=1;i<=10000000;++i) sum[i]=sum[i-1]+mul[i];
	for(int i=1;i<=2000;++i)
	 for(int j=i;j<=2000;j+=i)
	  dell[j].push_back(i);
}
int GetMul(int x)
{
	if(x<=10000000) return sum[x];
	if(MUL.count(x)) return MUL[x];
	int tmp=1;
	for(int l=2,r=0;l<=x;l=r+1)
	{
		r=x/(x/l);
		tmp-=(r-l+1)*GetMul(x/l); 
	}
	return MUL[x]=tmp;//记忆化
}
long long GetSum(int x,int y)
{
	long long tmp=0;
	for(int l=1,r=0;l<=min(x,y);l=r+1)
	{
		r=min(x/(x/l),y/(y/l));
		tmp+=(long long)(GetMul(r)-GetMul(l-1))*(long long)(x/l)*(long long)(y/l);
	}
	return tmp;
}
long long query(int x,int y,int z)
{
	if(x==0||y==0) return 0;
	if(vis.count((Node){x,y,z})) return vis[(Node){x,y,z}];
	if(z==1) 
	{
		long long tmp=GetSum(x,y);
		vis[(Node){x,y,z}]=vis[(Node){y,x,z}]=tmp;
		return tmp;
	}
	long long tmp=0;
	for(int i=0;i<(int)dell[z].size();++i)
	tmp+=(long long)mul[dell[z][i]]*query(y/dell[z][i],x,dell[z][i]);
	return vis[(Node){x,y,z}]=tmp;//记忆化
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);pre();
	MUL.clear();vis.clear();
	printf("%lld\n",query(n,m,k));
	return 0;
}