题解 P4140 【奇数国】

首先，按照题意，把前$60$个素数打出来$[2$ $-$ $281]$。

因为只有$60$个，再加上本宝宝极其懒得写线性筛于是每一个都$O(\sqrt{n})$暴力筛就好了。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n;

int main()

{

//    freopen("1.txt","w",stdout);

    printf("");//格式问题，以自己爱好稍作更改。

    for(int i=;i<=;i++)

    {

        for(int j=;j*j<=i;j++)

          if(i%j==) goto rp;

        printf(",%d",i),n++;

        rp:;

    }

    return ;

}

如果我们用$prime[i]$表示第i个素数。
筛出来是这样的：

int prime[]={

    ,,,,,,,,,

    ,,,,,,,

    ,,,,,,,

    ,,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,

};

---

之后，我们看清点存款操作，

问$[1,product]$里，有多少个$num$满足：

$$num*x+product*y=1$$

这，与我们素数的性质好像啊。

这就是 $num*x≡1$ $ $ $ $ $(mod$ $ $ $product)$

也就是 $gcd(num$ $,$ $product)$ $=$ $1$

嗯，好，问题转化成了：

求 $[1,product]$ 里，有多少个 $num$ 与 $product$ 互质。

也就是 $\varphi(product)$ 等于多少。

之后，根据欧拉函数的通式。

$$\varphi(n)=n*\prod_{p_i|n}(1-\frac{1}{p_i})=n*\prod_{p_i|n}\frac{p_i-1}{p_i}$$

看数据范围，又让 $mod$ $ $ $p$

所以，

再线性推一下逆元,

求解即可。

---

$ps:$ 如果脸黑被卡常数了的话，可以把 $[1-281]$ 的逆元打表。

大概代码是这样的：

    pni[]=;

    for(int i=;i<=;i++)

    pni[i]=(long long)(mod-mod/i)*pni[mod%i]%mod;

---

下面，就是区间维护。

题目中说了，~~（在出题人眼里）~~他们的加法相当于我们的乘法。

我们要维护区间 $[a,b]$ 的 “和” 记为 $product$

更改的是某个点（银行）$b_{i}$ 的存款

显然的线段树保存每段区间出现的质因子。

看题面，由于最多出现$60$个质数，我们用一个 $long$ $ $ $long$ 的每一位表示一个质数，然后用或运算$xor$即可实现 “加和” 相乘操作。

然后就……

好好的写代码吧。

不过……

模数为啥不是 $19260817$ 或者是 $998244353$ 或 $64123$ 呢……

---

$ps:$ 一定要看看线段树每次的区间边上判定 $!$ $!$ $!$

本宝宝调了两天 $……$

委屈巴巴。。。

---

上代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define mod 19961993

const int prime[]={

    ,,,,,,,,,

    ,,,,,,,

    ,,,,,,,

    ,,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,,,,,

    ,

};//记录质数。

int pni[];

    //线段树。

    struct data{

        long long sum;//区间（和）乘积

        long long p;//包含哪些素数。第i个二进制位如果是1，则有prime[i]这个素数,从1开始。

    }point[];

    data ans;//记录查询答案。

    void built(int l,int r,int o)

    {

        if(l==r) {point[o].sum=;point[o].p=;return ;}

        int mid=(l+r)/;

        built(l,mid,o*);

        built(mid+,r,o*+);

    //    printf("%d %d %d %d\n",l,r,o,mid);

        point[o].sum=point[o*].sum*point[o*+].sum%mod;

        point[o].p=;

    //     printf("%d %d\n",point[o].sum,point[o].p);

    }

    void chang(int l,int r,int o,const int t,const int k)//第t个点改为k

    {

//        printf("%d %d %d %d %d\n",&l,&r,&o,&t,&k);

        if(l==r){

            point[o].sum=k;

            long long p=;

            for(int i=;i<=;i++){

                if((k%prime[i])==) p|=1LL<<(i-);

                point[o].p=p;

            }

            return ;

        }

        int mid=(l+r)/;

        if(t<=mid) chang(l,mid,o*,t,k);

        else chang(mid+,r,o*+,t,k);

        point[o].sum=point[o*].sum*point[o*+].sum%mod;

        point[o].p=point[o*].p|point[o*+].p;

    }

    void quest(int l,int r,int o,int l1,int r1)//查询L到R。

    {

        if(l1<=l&&r<=r1){

            ans.sum=ans.sum*point[o].sum%mod;

            ans.p|=point[o].p;

            return ;

        }

        int mid=(l+r)/;

        if(l1<=mid) quest(l,mid,o*,l1,r1);

        if(mid<r1)  quest(mid+,r,o*+,l1,r1);

    }

//    void debug()

//    {

//        for(int i=1;i<=100;i++)

//        printf("%d %d %d\n",i,point[i].p,point[i].sum);

//    }

int main()

{

//    freopen("1.in","r",stdin);

//    freopen("1.out","w",stdout);

    built(,,);

    pni[]=;

    for(int i=;i<=;i++)

    pni[i]=(long long)(mod-mod/i)*pni[mod%i]%mod;

    //线性筛逆元

    int tt;

    scanf("%d",&tt);

    while(tt--)

    {

        int x;scanf("%d",&x);

        if(x)

        {

        int t,k;

        scanf("%d%d",&t,&k);

        chang(,,,t,k);

        }

        else

        {

            int l1,r1;

            ans.sum=;

            ans.p=;

            scanf("%d%d",&l1,&r1);

            quest(,,,l1,r1);

            long long f=ans.sum;

            for(int i=;i<=;i++)//计算φ

            if(ans.p&(1LL<<(i-))) f=f*(prime[i]-)%mod,f=f*pni[prime[i]]%mod;

            printf("%d\n",(int)f);

        }

//        debug();

    }

    return ;//程序拜拜

}

巴特西

题解 P4140 【奇数国】

最新文章

热门文章

巴特西

题解 P4140 【奇数国 】

最新文章

热门文章

题解 P4140 【奇数国】