首先，按照题意，把前60个素数打出来[2 − 281]。
因为只有60个，再加上本宝宝极其懒得写线性筛于是每一个都O(√n)暴力筛就好了。
代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n; int main() { // freopen("1.txt","w",stdout); printf("0");//格式问题，以自己爱好稍作更改。 for(int i=2;i<=281;i++) { for(int j=2;j*j<=i;j++) if(i%j==0) goto rp; printf(",%d",i),n++; rp:; } return 0; }
如果我们用prime[i]表示第i个素数。
筛出来是这样的：
int prime[61]={ 0,2,3,5,7,11,13,17,19, 23,29,31,37,41,43,47, 53,59,61,67,71,73,79, 83,89,97,101,103,107, 109,113,127,131,137, 139,149,151,157,163, 167,173,179,181,191, 193,197,199,211,223, 227,229,233,239,241, 251,257,263,269,271, 277,281 };
---
之后，我们看 清点存款 操作，
问[1,product]里，有多少个num满足：
num∗x+product∗y=1
这，与我们 素数的性质 好像啊。
这就是 num∗x≡1 (mod product)
也就是 gcd(num , product) = 1
嗯，好，问题转化成了：
求 [1,product] 里，有多少个 num 与 product 互质。
也就是 φ(product) 等于多少。
之后，根据欧拉函数的通式。
φ(n)=n∗∏pi|n(1−1pi)=n∗∏pi|npi−1pi
看数据范围，又让 mod p
所以，
再线性推一下逆元,
求解即可。
---
ps: 如果脸黑被卡常数了的话，可以把 [1−281] 的逆元打表。
大概代码是这样的：
pni[1]=1; for(int i=2;i<=281;i++) pni[i]=(long long)(mod-mod/i)*pni[mod%i]%mod;
---
下面，就是区间维护。
题目中说了，~~（在出题人眼里）~~他们的加法相当于我们的乘法。
我们要维护区间 [a,b] 的 “和” 记为 product
更改的是某个点（银行）bi 的存款
显然的线段树保存每段区间出现的质因子。
看题面，由于最多出现60个质数，我们用一个 long long 的每一位表示一个质数，然后用或运算xor即可实现 “加和” 相乘操作。
然后就……
好好的写代码吧。
不过……
模数为啥不是 19260817 或者是 998244353 或 64123 呢……
---
ps: 一定要看看线段树每次的区间边上判定 ! ! !
本宝宝调了两天 ……
委屈巴巴。。。
---
上代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define mod 19961993 const int prime[61]={ 0,2,3,5,7,11,13,17,19, 23,29,31,37,41,43,47, 53,59,61,67,71,73,79, 83,89,97,101,103,107, 109,113,127,131,137, 139,149,151,157,163, 167,173,179,181,191, 193,197,199,211,223, 227,229,233,239,241, 251,257,263,269,271, 277,281 };//记录质数。 int pni[300]; //线段树。 struct data{ long long sum;//区间（和）乘积 long long p;//包含哪些素数。第i个二进制位如果是1，则有prime[i]这个素数,从1开始。 }point[400010]; data ans;//记录查询答案。 void built(int l,int r,int o) { if(l==r) {point[o].sum=3;point[o].p=2;return ;} int mid=(l+r)/2; built(l,mid,o*2); built(mid+1,r,o*2+1); // printf("%d %d %d %d\n",l,r,o,mid); point[o].sum=point[o*2].sum*point[o*2+1].sum%mod; point[o].p=2; // 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=0; for(int i=1;i<=60;i++){ if((k%prime[i])==0) p|=1LL<<(i-1); point[o].p=p; } return ; } int mid=(l+r)/2; if(t<=mid) chang(l,mid,o*2,t,k); else chang(mid+1,r,o*2+1,t,k); point[o].sum=point[o*2].sum*point[o*2+1].sum%mod; point[o].p=point[o*2].p|point[o*2+1].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)/2; if(l1<=mid) quest(l,mid,o*2,l1,r1); if(mid<r1) quest(mid+1,r,o*2+1,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(1,100000,1); pni[1]=1; for(int i=2;i<=281;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(1,100000,1,t,k); } else { int l1,r1; ans.sum=1; ans.p=0; scanf("%d%d",&l1,&r1); quest(1,100000,1,l1,r1); long long f=ans.sum; for(int i=1;i<=60;i++)//计算φ if(ans.p&(1LL<<(i-1))) f=f*(prime[i]-1)%mod,f=f*pni[prime[i]]%mod; printf("%d\n",(int)f); } // debug(); } return 0;//程序拜拜 }
