【CF900D】Unusual Sequences

以你之姓@ 2023-10-11 11:16 31阅读 0赞

[题目][Link 1]

智力下降严重

显然要反演了呀

首先必须满足\\(x|y\\)，否则答案是\\(0\\)

我们枚举这个数列的\\(gcd\\)是\\(d\\)或者\\(d\\)的倍数

于是答案就是

\\\[\\sum\_\{x|d\}\[d|y\]\\mu(\\frac\{x\}\{d\})g(\\frac\{y\}\{d\})\\\]

\\(g(d)\\)表示和为\\(d\\)的正整数数列的数量，显然就是插一下板，于是\\(g(d)=\\sum\_\{i=1\}^d\\binom\{d-1\}\{i-1\}=2^\{d-1\}\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int mod=1e9+7;
    const int maxn=1e5+5;
    inline int ksm(int a,int b) {
        int S=1;
        for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
        return S;
    }
    int n,m,T,ans;
    int f[maxn],p[maxn>>1],mu[maxn];
    inline int getmu(int x) {
        if(x<=T) return mu[x];int now=0;
        for(re int i=1;i<=p[0]&&x!=1;++i) {
            if(x%p[i]) continue;
            x/=p[i];now^=1;
            if(x%p[i]==0) return 0;
        }
        if(x!=1) now^=1;
        if(!now) return 1;return -1;
    }
    inline void add(int i) {
        if(i%n) return;
        int x=getmu(i/n);
        if(x==1) ans=(ans+ksm(2,m/i-1))%mod;
        if(x==-1) ans=(ans-ksm(2,m/i-1)+mod)%mod;
    }
    int main() {
        scanf("%d%d",&n,&m);
        if(m%n) {puts("0");return 0;}
        T=std::ceil(std::sqrt(m/n));f[1]=mu[1]=1;
        for(re int i=2;i<=T;i++) {
            if(!f[i]) p[++p[0]]=i,mu[i]=-1;
            for(re int j=1;j<=p[0]&&p[j]*i<=T;++j) {
                f[p[j]*i]=1;if(i%p[j]==0) break;
                mu[p[j]*i]=-1*mu[i];
            }
        }
        for(re int i=1;i*i<=m;++i) {
            if(m%i) continue;
            add(i);if(m/i!=i) add(m/i);
        }
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11373482.html

[Link 1]: https://www.luogu.org/problem/CF900D