本文主要是介绍UESTC 1712 Easy Problem With Numbers 除法对和数取模，分解，线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
附上神牛原版思路：
如果这个题只有乘法，那么你肯定会做吧？线段树更新区间查找区间。
那么有除法呢？当一个数x和m互质的时候，除以x可以改为乘以x的逆元。（至于互质的数求逆元用扩展欧几里德，这个网上可以随便找到）
但是这题并不能保证除的数与m互质吧？什么时候x与m不互质呢？就是x与m含有公因子吧？
那么我们一开始就把m分解，分解出来m有p1,p2,p3,p4...pn等一些因子。
那么在这个题里面，每个数x都可以表示成p1^c1*p2^c2*p3^c3.....*pn^cn*A。这里A就是x去掉p1,p2,p3.。。等因子后的数，A与m就不含公因子了吧，就可以换成A与m的逆元。线段树里面呢，就维护c1,c2,c3.....和A的值。乘或除的时候c1,c2.。。就相应加或减。A就直接乘逆元就行了。其实就是一个线段树懒操作了，更新区间查找区间。
另外这里求逆元必须用扩展欧几里得，费马小定理只适用于mod为质数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define debug puts("======")
typedef long long ll;
using namespace std;
const int maxn=10005;
int n,q;
int tmp;
ll m;
char str[10];
int p[50];
int cnt;
struct Node
{int c[11];ll a;
}node[maxn<<2];
Node add[maxn<<2];
int no[maxn<<2];
void pre(int u)
{cnt=0;for(int i=2;i*i<=u;i++) {if(u%i==0)p[cnt++]=i;while(u&&u%i==0) {u/=i;}}if(u>1)p[cnt++]=u;
}
ll powMod(ll a,ll b)
{if(b==0) return 1;ll ans=powMod(a,b/2);ans=ans*ans%m;if(b&1)ans=ans*a%m;return ans;
}
ll ExGcd(ll a, ll b, ll &x, ll &y)
{if(b == 0){x = 1;y = 0;return a;}ll r = ExGcd(b, a % b, x, y);ll t = x;x = y;y = t - a / b * y;return r;
}
void pushUp(int rt)
{node[rt].a=node[rt<<1].a*node[rt<<1|1].a%m;for(int i=0;i<cnt;i++) {node[rt].c[i]=node[rt<<1].c[i]+node[rt<<1|1].c[i];}
}
void build(int l,int r,int rt)
{no[rt]=0;add[rt].a=1;for(int i=0;i<cnt;i++)add[rt].c[i]=0;if(l==r) {scanf("%d",&tmp);for(int i=0;i<cnt;i++) {node[rt].c[i]=0;while(tmp && tmp%p[i]==0) {tmp/=p[i];node[rt].c[i]++;}}node[rt].a=tmp;return;}int m=((l+r)>>1);build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushUp(rt);
}
void pushDown(int l,int r,int rt)
{if(no[rt]==0) return;no[rt]=0;int mm=((l+r)>>1);for(int i=0;i<cnt;i++) {add[rt<<1].c[i]+=add[rt].c[i];add[rt<<1|1].c[i]+=add[rt].c[i];node[rt<<1].c[i]+=add[rt].c[i]*(mm-l+1);node[rt<<1|1].c[i]+=add[rt].c[i]*(r-mm);add[rt].c[i]=0;}add[rt<<1].a=add[rt<<1].a*add[rt].a%m;add[rt<<1|1].a=add[rt<<1|1].a*add[rt].a%m;node[rt<<1].a=node[rt<<1].a*powMod(add[rt].a,mm-l+1)%m;node[rt<<1|1].a=node[rt<<1|1].a*powMod(add[rt].a,r-mm)%m;add[rt].a=1;no[rt<<1]=no[rt<<1|1]=1;
}
int num[20];
void update(int L,int R,int c,int l,int r,int rt,int ty)
{if(L<=l&&R>=r) {int u=c;for(int i=0;i<cnt;i++) {num[i]=0;// debug;while(u && u%p[i]==0) {u/=p[i];num[i]++;// debug;}}// debug;no[rt]=1;if(ty==0) {for(int i=0;i<cnt;i++) {add[rt].c[i]+=num[i];node[rt].c[i]+=num[i]*(r-l+1);}add[rt].a=add[rt].a*u%m;node[rt].a=node[rt].a*powMod(u,r-l+1)%m;}else {for(int i=0;i<cnt;i++) {add[rt].c[i]-=num[i];node[rt].c[i]-=num[i]*(r-l+1);}ll px,py;ExGcd(u, m, px, py); //求u的逆元，px为逆元px%=m;if(px<0) px+=m;add[rt].a=add[rt].a*px%m;node[rt].a=node[rt].a*powMod(px,r-l+1)%m;}return;}pushDown(l,r,rt);int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1,ty);if(R>m)update(L,R,c,m+1,r,rt<<1|1,ty);pushUp(rt);
}
ll query(int L,int R,int l,int r,int rt)
{if(L<=l&&R>=r) {ll ans=1;for(int i=0;i<cnt;i++) {ans=ans*powMod(p[i],node[rt].c[i])%m;}ans=ans*node[rt].a%m;return ans;}pushDown(l,r,rt);ll ans=1;int mm=(l+r)>>1;if(L<=mm)ans=ans*query(L,R,l,mm,rt<<1)%m;if(R>mm)ans=ans*query(L,R,mm+1,r,rt<<1|1)%m;return ans;
}
int main()
{int t;int a,b,c;int cas=1;scanf("%d",&t);while(t--) {scanf("%d%lld",&n,&m);pre(m);build(1,n,1);scanf("%d",&q);printf("Case #%d:\n",cas++);while(q--) {scanf("%s",str);if(str[0]=='M') {scanf("%d%d%d",&a,&b,&c);update(a,b,c,1,n,1,0);}else if(str[0]=='D') {scanf("%d%d%d",&a,&b,&c);update(a,b,c,1,n,1,1);}else {scanf("%d%d",&a,&b);printf("%lld\n",query(a,b,1,n,1));}}}return 0;
}这篇关于UESTC 1712 Easy Problem With Numbers 除法对和数取模，分解，线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
