首先,按照題意,把前$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("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$ 互質。
也就是 $\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[1]=1;
for(int i=2;i<=281;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[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;//程式拜拜
}