题解 P1587 【[NOI2016]循环之美】
Kelin
2018-01-25 21:04:25
题意:求$\sum_{x=1}^n\sum_{y=1}^m\frac{x}{y}$在$k$进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数
假设$\frac{x}{y}$的循环节长度为$l$
$\Rightarrow [\frac{xk^l}{y}]=[\frac{x}{y}]$
这里中括号表示其小数部分,意思就是把小数点往后挪$l$位,小数部分还是相同
比如$1.123123\ldots$小数点往后挪3位变成$1123.123\ldots$
参照10进制下小数点往后挪$l$位就是乘以$10^l$
那么$k$进制下小数点往后挪$l$位就是乘以$k^l$
$\Rightarrow \frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor=\frac{x}{y}-\lfloor\frac{x}{y}\rfloor$
$\Rightarrow xk^l-\lfloor\frac{xk^l}{y}\rfloor*y=x-\lfloor\frac{x}{y}\rfloor*y$
$\Rightarrow xk^l\equiv x\mod y$
题目要求最简分数,所以$(x,y)=1$
$\Rightarrow k^l\equiv1\mod y$
$\Rightarrow (k,y)=1$
$\Rightarrow Ans=\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1][(j,k)=1]$
那么接下来就有两条路可以走了
## 一:考虑处理$[(i,j)=1]$
(有公式恐惧症下转法二)
$\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1][(j,k)=1]$
$=\sum_{j=1}^m[(j,k)=1]\sum_{i=1}^n[(i,j)=1]$
$=\sum_{j=1}^m[(j,k)=1]\sum_{i=1}^n\sum_{d|(i,j)}\mu(d)$
$=\sum_{j=1}^m[(j,k)=1]\sum_{i=1}^n\sum_{d|i,d|j}\mu(d)$
$=\sum_{j=1}^m[(j,k)=1]\sum_{d|j}^n\mu(d)\frac{n}{d}$
$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{j=1}^m[d|j][(j,k)=1]$
$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{jd=1}^m[d|jd][(jd,k)=1]$
$j$用$jd$替换一下来减少限制(下同)
$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{j=1}^{\frac{m}{d}}[(jd,k)=1]$
$=\sum_{d=1}^n\mu(d)[(d,k)=1]\frac{n}{d}\sum_{j=1}^{\frac{m}{d}}[(j,k)=1]$
考虑$f(n)=\sum_{i=1}^n[(i,k)=1]=\frac{n}{k}\phi(k)+f(n\mod k)$
暴力$O(k\log k)\gcd$算一下$f(1)\ldots f(k)$
接下来貌似又有两条路可以走了
#### ①:考虑化简式子
考虑$g(n,k)=\sum_{d=1}^n\mu(d)[(d,k)=1]$
$=\sum_{d=1}^n\mu(d)\sum_{p|(d,k)}\mu(p)$
$=\sum_{d=1}^n\mu(d)\sum_{p|d,p|k}\mu(p)$
$=\sum_{d=1}^n\sum_{p|d}\mu(d)\sum_{p|k}\mu(p)$
$=\sum_{p|k}\mu(p)\sum_{dp=1}^n\sum_{p|dp}\mu(dp)$
$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(dp)$
如果$(d,p)\neq1$,那么$\mu(dp)=0$
$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,p)=1]$
$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(d)\mu(p)[(d,p)=1]$
$=\sum_{p|k}\mu(p)^2\sum_{d=1}^{\frac{n}{p}}\mu(d)[(d,p)=1]$
$=\sum_{p|k}\mu(p)^2g(\frac{n}{p},p)$
边界$g(0,k)=0$
$g(n,1)=\sum_{d=1}^n\mu(d)$直接杜教筛
复杂度是$O$(($k$的质因子个数)$\sqrt n+n^{\frac{2}{3}}$)
```c++
#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=7e5+5,E=2e6+5;
typedef int arr[N];typedef long long ll;
struct Am{int nx,x,w;}e1[E];
struct Ans{int nx,n,m,k;ll w;}e2[E];
int n,m,k,M,c1,c2,K[2000],f1[E],f2[E];arr is,pr,mu,Smu;
int Sm(int x){
if(x<=M)return Smu[x];
int u=(x+2017)%E;
for(int i=f1[u];i;i=e1[i].nx)if(e1[i].x==x)return e1[i].w;
e1[++c1]=Am{f1[u],x,1};f1[u]=c1;
int&w=e1[c1].w,i=2,j=sqrt(x);
for(;i<=j;++i)w-=Sm(x/i);
for(;i<=x;i=j+1)j=x/(x/i),w-=(j-i+1)*Sm(x/i);
return w;
}
ll sol(int n,int m,int k){
if(!n||!m)return 0;
int u=(2017ll*n+m+k)%E;
for(int i=f2[u];i;i=e2[i].nx)if(e2[i].n==n&&e2[i].m==m&&e2[i].k==k)return e2[i].w;
e2[++c2]=Ans{f2[u],n,m,k,0};f2[u]=c2;ll&w=e2[c2].w;
if(k==1){
if(n>m)swap(n,m);
int i=1,j=sqrt(n),s,t=0,x,y;
for(;i<=j;++i,t=s)s=Sm(i),w+=1ll*(n/i)*(m/i)*(s-t);
for(;i<=n;i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),s=Sm(j),w+=1ll*x*y*(s-t);
u=(2017ll*m+n+k)%E;e2[++c2]=Ans{f2[u],m,n,k,w};f2[u]=c2;
}else for(int i=1;i<=K[0]&&K[i]<=k;++i)
if(k%K[i]==0&&mu[K[i]])
w+=sol(m/K[i],n,K[i])*mu[K[i]];
return w;
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min(N-5,max(k,min(n,m)));Smu[1]=mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;if(i%pr[j])mu[x]=-mu[i];else break;
}Smu[i]=Smu[i-1]+mu[i];
}
fp(i,1,k)if(k%i==0)K[++K[0]]=i;
printf("%lld",sol(n,m,k));
return 0;
}
```
#### ②:考虑分析式子
我们可以把$k$表示成$p^aq$,假设$p$是$k$最小的质因子
对于1到$k$中每一个数可以预处理出他的$p,q$
$g(n,k)=\sum_{d=1}^n\mu(d)[(d,k)=1]=\sum_{d=1}^n\mu(d)[(d,p)=1][(d,q)=1]$
当$(d,q)=1$时只有$(d,p)=1,(d,p)=p$两种情况
所以我们可以转化为求满足$(d,q)=1$的$\mu(d)$减去$(d,q)=1$中满足$(d,p)=p$的$\mu(d)$
即$g(n,k)=\sum_{d=1}^n\mu(d)[(d,q)=1]-\sum_{d=1}^n\mu(d)[(d,q)=1][(d,p)=p]$
$=g(n,q)-\sum_{dp=1}^n\mu(dp)[(dp,q)=1][(dp,p)=p]$
$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,q)=1]$
当$(d,p)\neq1$时$\mu(dp)=0$,所以$d$要满足$(d,p)=1$
$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,p)=1][(d,q)=1]$
$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(d)\mu(p)[(d,k)=1]$
$=g(n,q)-\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(d)[(d,k)=1]$
$=g(n,q)+g(\frac{n}{p},k)$
边界和复杂度是同上
```c++
#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=1e6+5,E=2.2*N;
typedef int arr[N];
struct eg{int nx,n,k,w;}e[E];
int n,m,k,M,ce,fi[E],p[2001],q[2001];arr is,pr,mu,Smu,f;
int g(int n,int k){
if(!n||(n<=M&&k==1))return Smu[n];
int x=(1LL*n*2017+k)%E;
for(int i=fi[x];i;i=e[i].nx)if(e[i].n==n&&e[i].k==k)return e[i].w;
e[++ce]=eg{fi[x],n,k,0};fi[x]=ce;int&w=e[ce].w;
if(k==1){
w=1;int i=2,j=sqrt(n),x;
for(;i<=j;++i)w-=g(n/i,1);
for(;i<=n;i=j+1)x=n/i,j=n/x,w-=(j-i+1)*g(x,1);
}else w=g(n,q[k])+g(n/p[k],k);
return w;
}
int gcd(int a,int b){return!b?a:gcd(b,a%b);}
inline int Sf(int x){return x/k*f[k]+f[x%k];}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min(N-5,min(n,m));Smu[1]=mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;if(i%pr[j])mu[x]=-mu[i];else break;
}Smu[i]=Smu[i-1]+mu[i];
}
fp(i,1,k)f[i]=f[i-1]+(gcd(i,k)==1);
fp(i,2,k){
for(int j=2;;++j)if(i%j==0&&!is[j]){p[i]=j;break;}
for(q[i]=i;q[i]%p[i]==0;)q[i]/=p[i];
}
int i=1,j=sqrt(min(n,m)),x,y,s,t=0;long long w=0;
for(;i<=j;++i,t=s)s=g(i,k),w+=1ll*(n/i)*Sf(m/i)*(s-t);
for(;i<=min(n,m);i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),
s=g(j,k),w+=1ll*x*Sf(y)*(s-t);
printf("%lld",w);
return 0;
}
```
## 二:考虑处理$[(j,k)=1]$
令$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,k)}\mu(d) $
$=\sum_{i=1}^n\sum_{jd=1}^m[(i,jd)=1]\sum_{d|jd,d|k}\mu(d) $
$=\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^{\frac{m}{d}}[(i,jd)=1]$
$=\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^{\frac{m}{d}}[(i,j)=1][(i,d)=1]$
$=\sum_{d|k}\mu(d)f(\frac{m}{d},n,d)$
边界$f(0,m,k)=f(n,0,k)=0$
然后$k=1$就是简单处理一下$\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]=\sum_{d=1}^n\mu(d)\frac{n}{d}\frac{m}{d}$就$ok$了
复杂度是$O(\log n\log m\sqrt n+n^{\frac{2}{3}})$
```c++
#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define fd(i,a,b) for(int i=a,I=b;i>=I;--i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=1e7+5;
typedef int arr[N];
typedef long long ll;
struct da{int n,m,k;inline bool operator<(const da&b)const{return n==b.n?(m==b.m?k<b.k:m<b.m):n<b.n;}};
int n,m,k,M,K[2000];arr is,pr,mu,Smu;map<int,int>Am;map<da,ll>Ans;
int Sm(int x){
if(x<=M)return Smu[x];
if(Am[x])return Am[x];
int w=1,i=2,j=sqrt(x);
for(;i<=j;++i)w-=Sm(x/i);
for(;i<=x;i=j+1)j=x/(x/i),w-=(j-i+1)*Sm(x/i);
return Am[x]=w;
}
ll sol(int n,int m,int k){
if(!n||!m)return 0;
da now=da{n,m,k};
if(Ans[now])return Ans[now];ll w=0;
if(k==1){
if(n>m)swap(n,m);
int i=1,j=sqrt(n),s,t=0,x,y;
for(;i<=j;++i,t=s)s=Sm(i),w+=1ll*(n/i)*(m/i)*(s-t);
for(;i<=n;i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),s=Sm(j),w+=1ll*x*y*(s-t);
Ans[da{m,n,k}]=w;
}else for(int i=1;i<=K[0]&&K[i]<=k;++i)
if(k%K[i]==0&&mu[K[i]])
w+=sol(m/K[i],n,K[i])*mu[K[i]];
return Ans[now]=w;
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min((int)1e7,max(k,min(n,m)));mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;
if(i%pr[j])mu[x]=-mu[i];
else{mu[x]=0;break;}
}
}fp(i,1,M)Smu[i]=Smu[i-1]+mu[i];
fp(i,1,k)if(k%i==0)K[++K[0]]=i;
printf("%lld",sol(n,m,k));
return 0;
}
```
如果是考场我还是会选择法二的