1 条题解

  • 0
    @ 2025-8-24 21:26:48

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Kelin
    这个家伙太菜，没什么可以留下的

    搬运于2025-08-24 21:26:47，当前版本为作者最后更新于2018-01-25 21:04:25，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    题意:求∑x=1n∑y=1mxy\sum_{x=1}^n\sum_{y=1}^m\frac{x}{y}在kk进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数

    假设xy\frac{x}{y}的循环节长度为ll

    ⇒[xkly]=[xy]\Rightarrow [\frac{xk^l}{y}]=[\frac{x}{y}]

    这里中括号表示其小数部分,意思就是把小数点往后挪ll位,小数部分还是相同

    比如1.123123…1.123123\ldots小数点往后挪3位变成1123.123…1123.123\ldots

    参照10进制下小数点往后挪ll位就是乘以10l10^l

    那么kk进制下小数点往后挪ll位就是乘以klk^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$

    ⇒xkl≡xmod  y\Rightarrow xk^l\equiv x\mod y

    题目要求最简分数,所以(x,y)=1(x,y)=1

    ⇒kl≡1mod  y\Rightarrow k^l\equiv1\mod y

    ⇒(k,y)=1\Rightarrow (k,y)=1

    $\Rightarrow Ans=\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1][(j,k)=1]$

    那么接下来就有两条路可以走了

    一:考虑处理[(i,j)=1][(i,j)=1]

    (有公式恐惧症下转法二)

    ∑i=1n∑j=1m[(i,j)=1][(j,k)=1]\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1][(j,k)=1]

    =∑j=1m[(j,k)=1]∑i=1n[(i,j)=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]$

    jj用jdjd替换一下来减少限制(下同)

    $=\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(klog⁡k)gcd⁡O(k\log k)\gcd算一下f(1)…f(k)f(1)\ldots f(k)

    接下来貌似又有两条路可以走了

    ①:考虑化简式子

    考虑g(n,k)=∑d=1nμ(d)[(d,k)=1]g(n,k)=\sum_{d=1}^n\mu(d)[(d,k)=1]

    =∑d=1nμ(d)∑p∣(d,k)μ(p)=\sum_{d=1}^n\mu(d)\sum_{p|(d,k)}\mu(p)

    =∑d=1nμ(d)∑p∣d,p∣kμ(p)=\sum_{d=1}^n\mu(d)\sum_{p|d,p|k}\mu(p)

    =∑d=1n∑p∣dμ(d)∑p∣kμ(p)=\sum_{d=1}^n\sum_{p|d}\mu(d)\sum_{p|k}\mu(p)

    =∑p∣kμ(p)∑dp=1n∑p∣dpμ(dp)=\sum_{p|k}\mu(p)\sum_{dp=1}^n\sum_{p|dp}\mu(dp)

    =∑p∣kμ(p)∑d=1npμ(dp)=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(dp)

    如果(d,p)≠1(d,p)\neq1,那么μ(dp)=0\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]$

    =∑p∣kμ(p)2g(np,p)=\sum_{p|k}\mu(p)^2g(\frac{n}{p},p)

    边界g(0,k)=0g(0,k)=0

    g(n,1)=∑d=1nμ(d)g(n,1)=\sum_{d=1}^n\mu(d)直接杜教筛

    复杂度是OO((kk的质因子个数)n+n23\sqrt n+n^{\frac{2}{3}})

    #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;
}

    ②:考虑分析式子

    我们可以把kk表示成paqp^aq,假设pp是kk最小的质因子

    对于1到kk中每一个数可以预处理出他的p,qp,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,q)=1时只有(d,p)=1,(d,p)=p(d,p)=1,(d,p)=p两种情况

    所以我们可以转化为求满足(d,q)=1(d,q)=1的μ(d)\mu(d)减去(d,q)=1(d,q)=1中满足(d,p)=p(d,p)=p的μ(d)\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)−∑dp=1nμ(dp)[(dp,q)=1][(dp,p)=p]=g(n,q)-\sum_{dp=1}^n\mu(dp)[(dp,q)=1][(dp,p)=p]

    =g(n,q)−∑d=1npμ(dp)[(d,q)=1]=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,q)=1]

    当(d,p)≠1(d,p)\neq1时μ(dp)=0\mu(dp)=0,所以dd要满足(d,p)=1(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(np,k)=g(n,q)+g(\frac{n}{p},k)

    边界和复杂度是同上

    #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][(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]$

    =∑d∣kμ(d)f(md,n,d)=\sum_{d|k}\mu(d)f(\frac{m}{d},n,d)

    边界f(0,m,k)=f(n,0,k)=0f(0,m,k)=f(n,0,k)=0

    然后k=1k=1就是简单处理一下$\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]=\sum_{d=1}^n\mu(d)\frac{n}{d}\frac{m}{d}$就okok了

    复杂度是O(log⁡nlog⁡mn+n23)O(\log n\log m\sqrt n+n^{\frac{2}{3}})

    #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;
}

    如果是考场我还是会选择法二的

    • 1

    [NOI2016] 循环之美

    信息

    ID
    580
    时间
    2000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 31ms