bzoj4652
这道题感觉非常优美……能有一个这么优美的题面和较高的思维难度真的不容易……
为了表示方便，让我先讲一下两个符号。[a][a]表示如果aa为真，那么返回11，否则返回00； a⊥ba⊥b表示aa与bb互质。
首先，我们需要考虑一个分数要成为纯循环小数需要满足什么条件。
我们先来回想一下，我们是怎样使用除法来判断一个分数xyxy是否是纯循环小数的。显然我们是一路除下去，什么时候出现了相同的余数，那么这个数就是一个循环小数。如果第一个重复的余数是xx，那么这个数就是纯循环小数。这种方法实际上就是存在一个数l≠0l≠0，使得：
xkl≡x(mody)xkl≡x(mody)
又由于题目要求值不重复，那么我们可以得到x⊥yx⊥y。所以，我们可以推出kl≡1(mody)kl≡1(mody)。所以我们只需k⊥yk⊥y即可。
于是，我们实际上是要求这个式子：
=∑x=1n∑y=1m[x⊥y][y⊥k]∑y=1m[y⊥k]∑x=1n[x⊥y]∑x=1n∑y=1m[x⊥y][y⊥k]=∑y=1m[y⊥k]∑x=1n[x⊥y]
用一下莫比乌斯反演，可以得到：
=∑y=1m[y⊥k]∑x=1n∑d|x,d|yμ(d)∑y=1m[y⊥k]∑d|ynμ(d)⌊nd⌋∑y=1m[y⊥k]∑x=1n∑d|x,d|yμ(d)=∑y=1m[y⊥k]∑d|ynμ(d)⌊nd⌋
再通过换一下枚举顺序，可得：
==∑d=1nμ(d)⌊nd⌋∑y=1m[d | y][y⊥k]∑d=1nμ(d)⌊nd⌋∑i=1⌊md⌋[id⊥k]∑d=1n[d⊥k]μ(d)⌊nd⌋∑i=1⌊md⌋[i⊥k]∑d=1nμ(d)⌊nd⌋∑y=1m[d | y][y⊥k]=∑d=1nμ(d)⌊nd⌋∑i=1⌊md⌋[id⊥k]=∑d=1n[d⊥k]μ(d)⌊nd⌋∑i=1⌊md⌋[i⊥k]
最后一步用了互质的一个性质，那就是[ab⊥c]=[a⊥c][b⊥c][ab⊥c]=[a⊥c][b⊥c]。这点应该很好理解吧。
我们不妨设f(n,k)=∑ni=1[i⊥k]f(n,k)=∑i=1n[i⊥k]，那么我们只要在O(1)O(1)的时间内求出ff，复杂度就是O(n)O(n)，就可以得到8484分。实际上，我们可以得到一个式子：
f(n,k)=⌊nk⌋f(k,k)+f(nmodk,k)f(n,k)=⌊nk⌋f(k,k)+f(nmodk,k)
这个应该也不难理解，因为[a⊥b]=[amodb⊥b][a⊥b]=[amodb⊥b]
于是我们就可以对f(n,k)f(n,k)预处理出n≤kn≤k的值，每次求值就变成O(1)O(1)了。于是8484分到手了。
我们考虑接下来该如何优化。由于⌊mx⌋⌊mx⌋只有m−−√m种取值，⌊nx⌋⌊nx⌋只有n√n种取值，于是我们显然可以分段求和。然后，我们就需要快速求出∑ni=1[i⊥k]μ(i)∑i=1n[i⊥k]μ(i)的值。
不妨设g(n,k)=∑ni=1[i⊥k]μ(i)g(n,k)=∑i=1n[i⊥k]μ(i)，我们来考虑一下这个函数如何快速求。我们先考虑kk的一个质因数pp，那么kk显然可以写成pcqpcq的形式。由于在[1,n][1,n]的范围中只有与kk互质的才是有效值，那么若x⊥kx⊥k，我们可以得到x⊥px⊥p并且x⊥qx⊥q。于是，我们可以考虑从x⊥qx⊥q的取值中减去xx不与pp互质的部分，就可以得到x⊥kx⊥k的部分。这里如果不懂的话可以自己画一个x⊥qx⊥q，x⊥px⊥p，x⊥kx⊥k的关系图理解一下。
由于所有与qq互质的数一定可以写成pxy(y⊥q)pxy(y⊥q)的形式。那么我们需要减去的数一定满足x>0x>0。又由于当x>1x>1时μ(pxy)=0μ(pxy)=0，所以我们只需要考虑x=1x=1的情况即可。在这种情况下，我们需要考虑的数就是py(y⊥q)py(y⊥q)的形式，所以我们可以得到如下式子：
g(n,k)=∑i=1n[i⊥q]μ(i)−∑y=1⌊np⌋[py⊥q]μ(py)=g(n,q)−∑y=1⌊np⌋[y⊥q]μ(py)g(n,k)=∑i=1n[i⊥q]μ(i)−∑y=1⌊np⌋[py⊥q]μ(py)=g(n,q)−∑y=1⌊np⌋[y⊥q]μ(py)
上面的最后一步是由于p⊥qp⊥q，所以py⊥qpy⊥q只需在保证y⊥qy⊥q即可。
我们接着来考虑后一个式子。显然当p⊥yp⊥y的时候μ(py)=μ(p)μ(y)μ(py)=μ(p)μ(y)，否则μ(py)=0μ(py)=0。于是，我们又得到了：
g(n,k)=g(n,q)−∑y=1⌊np⌋[y⊥p][y⊥q]μ(p)μ(y)=g(n,q)−μ(p)∑y=1⌊np⌋[y⊥k]μ(y)=g(n,q)+g(⌊np⌋,k)g(n,k)=g(n,q)−∑y=1⌊np⌋[y⊥p][y⊥q]μ(p)μ(y)=g(n,q)−μ(p)∑y=1⌊np⌋[y⊥k]μ(y)=g(n,q)+g(⌊np⌋,k)
于是我们就可以递归求解了。容易发现边界情况就是n=0n=0或者k=1k=1。n=0n=0的时候直接返回00就可以了，k=1k=1的时候就是莫比乌斯函数的前缀和，用杜教筛求出来就可以了。由于每次递归要么nn会变成⌊np⌋⌊np⌋，有O(n√)O(n)种取值；要么pp少了一个质因数，有ω(k)ω(k)种取值，所以总共有O(ω(k)n√)O(ω(k)n)种取值，记忆化搜索即可。其中ω(k)ω(k)表示kk的不同的质因子数目。于是最后的总复杂度为O(ω(k)n√+n23)O(ω(k)n+n23)，可以通过此题。
两个细节：
可以在递归求gg的时候不直接记kk，而是记录kk还剩下多少个质因数，方便存储；
记忆化的时候可以开哈希链表存储，用mapmap也可以，或者干脆分n,mn,m以及小于、大于根号的情况存储也可以。
第一次写这种题的题解，好像写得过于详细了(其实是因为我什么都不会)，请大神们不要喷……
下面贴代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
#define long long long
#define to i*prime[j]
#define maxn 1000005
long n,m,k;
int p;
int miu[maxn];
int prime[maxn];
int sum[maxn];
int k_prf[10];
bool sift[maxn];
map<int,int> mp;
map<int,int> ms[10];
map<int,int> mt[10];
void init()
{
miu[1]=sum[1]=1;
for(int i=2;i<maxn;i++)
{
if(!sift[i])
{
prime[++p]=i;
miu[i]=-1;
}
sum[i]=sum[i-1]+miu[i];
for(int j=1;j<=p&&to<maxn;j++)
{
sift[to]=true;
if(i%prime[j]==0)
{
miu[to]=0;
break;
}
else miu[to]=-miu[i];
}
}
}
int sum_miu(int x)
{
if(x<maxn) return sum[x];
if(mp.count(x)) return mp[x];
int ans=1;
for(int i=2,p;p<x;i=p+1)
{
p=x/(x/i);
ans-=sum_miu(x/i)*(p-i+1);
}
return mp[x]=ans;
}
long S(int x,int r)//sum_miu of 1~r coprime with the first x-th prmfactors of k
{
if(!x) return sum_miu(r);
if(r<=1) return r;
if(ms[x].count(r)) return ms[x][r];
return ms[x][r]=S(x-1,r)+S(x,r/k_prf[x]);
}
int T(int x,int r)//numbers of 1~r ...
{
if(!x) return r;
if(r<=1) return r;
if(mt[x].count(r)) return mt[x][r];
return mt[x][r]=T(x-1,r)-T(x-1,r/k_prf[x]);
}
int main()
{
init();
scanf("%lld%lld%lld",&n,&m,&k);
int kk=k;
p=0;
for(int i=1;kk>1;i++)
{
if(kk%prime[i]==0)
{
k_prf[++p]=prime[i];
while(kk%prime[i]==0)
kk/=prime[i];
}
}
long ans=0ll;
for(int i=1,t;i<=n&&i<=m;i=t+1)
{
t=min(m/(m/i),n/(n/i));
ans+=(n/i)*(S(p,t)-S(p,i-1))*T(p,m/i);
}
printf("%lld",ans);
}
评论