http://www.elijahqi.win/archives/3274
题意：每次乘一个数每次除一个以前乘过的数，每次询问求总答案 模数不为质数且不一定于前面的互质
线段树，以位置建树即可 每次除法相当于把以前的位置改成1即可
#include<cstdio> #include<cctype> #define lc (x<<1) #define rc (x<<1|1) #include<algorithm> #define ll long long using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int N=1e5+10; struct node{int sum;}tree[N<<2];int mod; inline void update(int x){tree[x].sum=(ll)tree[lc].sum*tree[rc].sum%mod;} inline void modify(int x,int l,int r,int p,int v){ if (l==r) {tree[x].sum=v;return;}int mid=l+r>>1; if (p<=mid) modify(lc,l,mid,p,v);else modify(rc,mid+1,r,p,v);update(x); } inline void build(int x,int l,int r){ tree[x].sum=1;if (l==r) return;int mid=l+r>>1; build(lc,l,mid);build(rc,mid+1,r); } int main(){ freopen("cal.in","r",stdin); freopen("cal.out","w",stdout); int T=read(); while(T--){ int q=read();mod=read();build(1,1,q); for (int owo=1;owo<=q;++owo){ int op=read(); if (op==1) modify(1,1,q,owo,read()),printf("%d\n",tree[1].sum); else modify(1,1,q,read(),1),printf("%d\n",tree[1].sum); } } return 0; }辣鸡elijahqi考场做法
#include<map> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstring> #define pa pair<int,int> #include<algorithm> #define ll long long using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int N=100010; int T,prime[N],m_prime[N],cnt,nm[N],pos[N],p1[N],inv[N],Q,mod,tot; bool not_prime[N],flag[N];ll ans;map<int,int> mm; map<int,int>::iterator it; inline int ksm(ll b,int t){static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp; } inline void exgcd(int a,int b,int &x,int &y){ if (!b) {x=1;y=0;return;}exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } inline int gcd(int x,int y){ if(!y) return x;return gcd(y,x%y); } inline void gao(int m){ int x=m; for (int i=1;i<=tot&&prime[i]<=x;++i){ if (x%prime[i]) continue; if(flag[prime[i]]){ while(x%prime[i]==0) ++nm[p1[prime[i]]],x/=prime[i]; }else{ while(x%prime[i]==0) ans=ans*prime[i]%mod,x/=prime[i]; } } if (x>1) { if(x==m_prime[cnt]) ++nm[cnt]; else if (gcd(x,mod)==1)ans=ans*x%mod; else ++mm[x]; }ll ans1=ans; for (int i=1;i<=cnt;++i) ans1=ans1*ksm(m_prime[i],nm[i])%mod; for (it=mm.begin();it!=mm.end();++it){ ans1=ans1*ksm(it->first,it->second); }printf("%lld\n",ans1); } inline int get_inv(int a,int b){ static int t1,t2; exgcd(a,b,t1,t2); t1=(t1%b+b)%b; return t1; } inline void gao1(int p){ int m=pos[p];int x=m; for (int i=1;i<=tot&&prime[i]<=x;++i){ if (x%prime[i]) continue; if (flag[prime[i]]){ while(x%prime[i]==0) --nm[p1[prime[i]]],x/=prime[i]; }else{ while(x%prime[i]==0) ans=ans*inv[i]%mod,x/=prime[i]; } }if (x>1) { if (x==m_prime[cnt]) --nm[cnt]; else if (gcd(x,mod)==1) ans=ans*get_inv(x,mod)%mod; else{ --mm[x]; } }ll ans1=ans; for (int i=1;i<=cnt;++i) ans1=ans1*ksm(m_prime[i],nm[i])%mod; for (it=mm.begin();it!=mm.end();++it){ ans1=ans1*ksm(it->first,it->second); }printf("%lld\n",ans1); } int main(){ freopen("cal.in","r",stdin); freopen("cal.out","w",stdout); T=read(); for (int i=2;i<=1e5;++i) { if (!not_prime[i]) prime[++tot]=i; for (int j=1;prime[j]*i<=1e5&&j<=tot;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0) break; } } while(T--){ Q=read();mod=read();int x=mod;ans=1;cnt=0;mm.clear(); memset(nm,0,sizeof(nm));memset(flag,0,sizeof(flag)); memset(inv,0,sizeof(inv));memset(pos,0,sizeof(pos)); for (int i=1;i<=tot&&x>=prime[i];++i){ if (x%prime[i]) continue; m_prime[++cnt]=prime[i];p1[prime[i]]=cnt;flag[prime[i]]=1; while(x%prime[i]==0) x/=prime[i]; }if (x>1) m_prime[++cnt]=x; //for (int i=1;i<=cnt;++i) printf("%d ",m_prime[i]);puts(""); for (int i=1;i<=tot;++i){ if (flag[prime[i]]) continue; //printf("%d\n",get_inv(prime[i],mod)); inv[i]=get_inv(prime[i],mod); } for (int owo=1;owo<=Q;++owo){ int op=read(),m=read();pos[owo]=m; if (op==1)gao(m);else gao1(m); // printf("%d\n",ans); } } return 0; }