M_sea

洛谷5285 [十二省联考2019]骗分过样例
LuoguBZOJLOJ分析这是一道毒瘤题(迫真)。首先要感谢各位聚聚的题解,不然这题我是做不出的。$\textt...
扫描右侧二维码阅读全文
01
2019/05

洛谷5285 [十二省联考2019]骗分过样例

Luogu

BZOJ

LOJ

分析

这是一道毒瘤题(迫真)。

首先要感谢各位聚聚的题解,不然这题我是做不出的。

$\texttt{1_998244353}$

观察数据,显然要求的是 $19^x\mod 998244353$ 。

因为 $x$ 非常大,根据欧拉定理可以把 $x$ 对 $\varphi(998244353)=998244352$ 取模再快速幂。

$\texttt{1?}$

仍然要求 $19^x$ ,但是模数未知。

暴力可以得到模数为 $1145141$ 。

$\texttt{1?+}$

$\texttt{+}$ 表示模数很大。

根据一些方式可以得到,模数为 $5211600617818708273$ 。

具体方法戳这里

$\texttt{1wa_998244353}$

根据提示内的内容,可以想到这是算 $19^x$ 时爆了 $\mathrm{int}$ 。

可以发现存在一个循环节,那么预处理出来就可以直接算了。

$\texttt{2p}$

判质数。直接 $\mathrm{miller\_rabin}$ 即可。

$\texttt{2u}$

求莫比乌斯函数。

我们首先筛出 $10^6$ 内的质数,这样子 $x$ 最多还会有 $2$ 个质因子没有被处理。

那么先判断这两个质因子是否相等、再用 $\mathrm{miller\_rabin}$ 判断它是否为质数即可。

这个点很容易 $\mathrm{T}$ ,但是通过面向数据编程可以发现只用 $24251$ 做二次探测就可以过了。

$\texttt{2g}$

求原根。

先对 $\varphi(p)$ 分解质因数为 $p_1^{c_1}p_2^{c_2}...p_k^{c_k}$ 。

如果所有质因子 $p_i$ 都满足 $a^{\frac{\varphi(p)}{p_i}}=1$ ,那么 $a$ 就是 $p$ 的一个原根。这么做的时间复杂度是 $O(nk\log p)$ 的。

或者可以先找到一个原根 $g$ ,然后所有满足 $\gcd(i,\varphi(p))=1$ 的 $i$ 对应的 $g^i$ 都是原根。这么做的时间复杂度为 $O(p\log p)$ 。

$\texttt{2g+}$

这个模数的话,可以先筛出对应区间的质数,然后一个个判断来求。据说 5h 可以跑出来

通过看题解可得模数为 $1515343657$ 。那么直接用 $\texttt{2g}$ 的方法二求就行了。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <bits/stdc++.h>
#define re register
typedef long long ll;
using namespace std;

char op[20]; 

namespace task1 { //1_998244353 / 1? / 1?+
    ll mod;
    
    inline ll mul(ll x,ll y) {
        return (x*y-(ll)((long double)x/mod*y+0.5)*mod+mod)%mod;
    }
    
    inline ll read() {
        ll X=0; char c=getchar();
        while (c<'0'||c>'9') c=getchar();
        while (c>='0'&&c<='9') X=(X*10+c-'0')%(mod-1),c=getchar();
        return X;
    }

    inline ll qpow(ll a,ll b) {
        ll c=1;
        for (;b;b>>=1,a=mul(a,a))
            if (b&1) c=mul(c,a);
        return c;
    }
    
    inline void work() {
        if (op[1]=='_') mod=998244353ll;
        else if (op[2]=='+') mod=5211600617818708273ll;
        else mod=1145141ll;
        int T=read();
        while (T--) {
            ll x=read();
            printf("%lld\n",qpow(19,x));
        }
    }
}

namespace task2 { //1wa_998244353
    const int mod=998244353;

    int pw[200010];
    map<int,int> S;
    
    inline void work() {
        pw[0]=1,S[1]=0; int st,len;
        for (re int i=1;;++i) {
            pw[i]=pw[i-1]*19%mod;
            if (S.count(pw[i])) {
                st=S[pw[i]],len=i-st;
                break;
            }
            S[pw[i]]=i;
        }
        int T; scanf("%d",&T);
        while (T--) {
            ll x; scanf("%lld",&x);
            if (x<st) printf("%d\n",pw[x]);
            else printf("%d\n",pw[st+(x-st)%len]);
        }
    }
}

namespace task3 { //2p
    inline ll mul(ll x,ll y,ll mod) {
        return (x*y-(ll)((long double)x/mod*y+0.5)*mod+mod)%mod;
    }

    inline ll qpow(ll a,ll b,ll mod) {
        ll c=1;
        for (;b;b>>=1,a=mul(a,a,mod))
            if (b&1) c=mul(c,a,mod);
        return c;
    }
    
    inline int miller_rabin(ll n) {
        static int p[7]={2,3,5,7,11,13,24251},p_cnt=7; 
        
        if (n==1) return 0;
        if (n==2||n==3||n==5) return 1;
        if (!(n&1)||!(n%3)||!(n%5)) return 0;
        
        ll m=n-1; int k=0;
        while (!(m&1)) m>>=1,++k;
        for (re int ip=0;ip<p_cnt&&p[ip]<n;++ip) {
            ll x=qpow(p[ip],m,n),y=x;
            for (re int i=0;i<k;++i) {
                x=mul(x,x,n);
                if (x==1&&y!=1&&y!=n-1) return 0;
                y=x;
            }
            if (x!=1) return 0;
        }
        return 1;
    }

    inline void work() {
        int T; scanf("%d",&T);
        while (T--) {
            ll l,r; scanf("%lld%lld",&l,&r);
            for (re ll i=l;i<=r;++i) putchar(".p"[miller_rabin(i)]);
            puts("");
        }
    }
}

namespace task4 { //2u
    
    inline ll mul(ll x,ll y,ll mod) {
        return (x*y-(ll)((long double)x/mod*y+0.5)*mod+mod)%mod;
    }

    inline ll qpow(ll a,ll b,ll mod) {
        ll c=1;
        for (;b;b>>=1,a=mul(a,a,mod))
            if (b&1) c=mul(c,a,mod);
        return c;
    }
    
    inline int miller_rabin(ll n) {
        static int p[5]={2,3,5,7,24251},p_cnt=5;
        
        if (n==1) return 0;
        if (n==2||n==3||n==5) return 1;
        if (!(n&1)||!(n%3)||!(n%5)) return 0;
        
        ll m=n-1; int k=0;
        while (!(m&1)) m>>=1,++k;
        for (re int ip=4;ip<p_cnt&&p[ip]<n;++ip) {
            ll x=qpow(p[ip],m,n),y=x;
            for (re int i=0;i<k;++i) {
                x=mul(x,x,n);
                if (x==1&&y!=1&&y!=n-1) return 0;
                y=x;
            }
            if (x!=1) return 0;
        }
        return 1;
    }
    
    int v[1000010],p[1000010],cnt=0;
    int mu[1000010]; ll num[1000010];

    inline void work() {
        int T; scanf("%d",&T);
        while (T--) {
            ll l,r; scanf("%lld%lld",&l,&r);
            for (re ll i=l;i<=r;++i) mu[i-l+1]=1,num[i-l+1]=i,v[i-l+1]=0;
            int n=r-l+1;
            for (re int i=2;i<=n;++i) {
                if (!v[i]) {
                    p[++cnt]=i;
                    for (re ll j=(l+i-1)/i*i;j<=r;j+=i) {
                        if ((num[j-l+1]/i)%i==0) mu[j-l+1]=0;
                        else mu[j-l+1]=-mu[j-l+1];
                        while (num[j-l+1]%i==0) num[j-l+1]/=i;
                    }
                }
                for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
                    v[i*p[j]]=1;
                    if (i%p[j]==0) break;
                }
            }
            for (re int i=1;i<=n;++i) {
                if (!mu[i]||num[i]==1) continue;
                if (miller_rabin(num[i])) mu[i]=-mu[i];
                else if ((ll)sqrt(num[i])*(ll)sqrt(num[i])==num[i]) mu[i]=0;
            }
            for (re int i=1;i<=n;++i) putchar("-0+"[mu[i]+1]);
            puts("");
        }
    }
}

namespace task5 { //2g / 2g+
    int mod;
    int p[20],cnt;
    int vis[15000000],id[15000000];

    inline void fact(int x) {
        cnt=0;
        for (re int i=2;i*i<=x;++i) {
            if (x%i) continue;
            p[++cnt]=i;
            while (x%i==0) x/=i;
        }
        if (x>1) p[++cnt]=x;
    }
    
    inline int qpow(int a,int b) {
        int c=1;
        for (;b;b>>=1,a=1ll*a*a%mod)
            if (b&1) c=1ll*c*a%mod;
        return c;
    }
    
    inline int check(int x) {
        for (re int i=1;i<=cnt;++i)
            if (qpow(x,(mod-1)/p[i])==1) return 0;
        return 1;
    }

    inline int getg() {
        for (re int i=2;;++i)
            if (check(i)) return i;
    }
    
    inline void work() {
        int T; scanf("%d",&T);
        while (T--) {
            int l,r; scanf("%d%d",&l,&r);
            if (r==234133333) mod=1515343657;
            else scanf("%d",&mod);
            fact(mod-1);
            if (r-l<=1e6) {
                for (re int i=l;i<=r;++i) putchar(".g"[check(i)]);
                puts("");
            } else {
                memset(vis,0,sizeof(vis));
                for (re int i=1;i<=cnt;++i)
                    for (re int j=p[i];j<mod;j+=p[i])
                        vis[j]=1;
                int g=getg();
                for (re int i=1,pw=g;i<mod;++i,pw=1ll*pw*g%mod) id[pw]=i;
                for (re int i=l;i<=r;++i) putchar("g."[vis[id[i]]]);
                puts("");
            }
        }
    }
}

int main() {
    scanf("%s\n",op);
    if (op[0]=='1') {
        if (op[1]=='w') task2::work();
        else task1::work();
    }
    else if (op[1]=='p') task3::work();
    else if (op[1]=='u') task4::work();
    else if (op[1]=='g') task5::work();
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 04 PM

1 条评论

  1. smy

    sdl tql wsl

发表评论