找专业做网站,广东建设监理协会网站,电脑制作网页用什么软件,网站制作设计报价解析
洛谷你恶事做尽#xff01; 第三个tag在LOJ、bzoj等都是不需要的… 但在洛谷三只log根本过不去… 我谔谔。
如果做过 上帝与集合的正确用法 #xff0c;那么本题就并不难了。 打个表就可以发现#xff0c;不断取欧拉函数的上限只有log级别#xff0c;这使得我们暴力…解析
洛谷你恶事做尽 第三个tag在LOJ、bzoj等都是不需要的… 但在洛谷三只log根本过不去… 我谔谔。
如果做过 上帝与集合的正确用法 那么本题就并不难了。 打个表就可以发现不断取欧拉函数的上限只有log级别这使得我们暴力修改线段树复杂度就是正确的。
然后就做完了 不 这题也暴露了我数论知识及其不扎实的事实拓展欧拉定理的完整内容为 xb≡xb(modp)(bφ(p))x^b\equiv x^b\pmod p(b\varphi(p))xb≡xb(modp)(bφ(p)) xb≡xb%φ(p)φ(p)(modp)(b≥φ(p))x^b\equiv x^{b\%\varphi(p)\varphi(p)}\pmod p(b\ge\varphi(p))xb≡xb%φ(p)φ(p)(modp)(b≥φ(p)) 上帝那个题之所以可以直接当第二条来做是因为我们认为要求的那个东西绝对大于 φ(p)\varphi(p)φ(p)的。 本题则不然。 所以还需要在上一层快速幂的时候判断以下是否取过模即是否达到了 φ(p)\varphi(p)φ(p)。 总复杂度 O(nlog3n)O(n\log^3n)O(nlog3n)。
然后就做完了 不 这个代码已经可以在LOJ上AC但在洛谷打死也T#11。 我们发现我们每次快速幂的时候的底数都是固定的模数也就只是 ppp 不断取欧拉函数得到的 O(log)O(\log)O(log) 个数而已。 所以我们可以对每个模数预处理出光速幂这样就可以把快速幂的log拿掉了。 别忘了快速幂里还要判断是否取模。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
const int M2e5100;
const int inf1e9;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
bool flag;
const int B4e4100;
struct KSM{int c,mod,w;ll mi[B],Mi[B];bool jd[B],Jd[B];void init(int C,int Mod){cC;modMod;wsqrt(2*mod);mi[0]1;for(int i1;iw;i){mi[i]mi[i-1]*c;jd[i]jd[i-1];if(mi[i]mod){mi[i]%mod;jd[i]1;}}Mi[0]1;Mi[1]mi[w];Jd[1]jd[w];for(int i2;i2*mod/w;i){Mi[i]Mi[i-1]*Mi[1];Jd[i]Jd[i-1];if(Mi[i]mod){Mi[i]%mod;Jd[i]1;}}}inline ll calc(ll k){if(k2*mod){printf(k%lld mod%d\n,k,mod);}ll resMi[k/w]*mi[k%w];flagJd[k/w]|jd[k%w];if(resmod){res%mod;flag1;} //printf( k%lld mod%d %d %d jd%d %d res%lld\n,k,mod,k/w,k%w,Jd[k/w],jd[k%w],res);return res;}
}ksm[40];inline int getphi(int x){int ansx,topsqrt(x);for(int i2;itop;i){if(x%i) continue;ans1ll*ans*(i-1)/i;while(x%i0) x/i;}if(x1){ans1ll*ans*(x-1)/x;}return ans;
}int n,m,mod,c;int w[105];
inline int Solve(int k,int lim,int x,int mod){if(klim){ flagxmod; return x%mod;}if(mod1){flag1;return 0;}int phiw[k],preSolve(k1,lim,x,phi);//printf( k%d pre%d phi%d mod%d flag%d mymod%d\n,k,pre,phi,mod,flag,ksm[k].mod);//if(preflag*phiksm[k].mod*2){// printf( k%d pre%d phi%d mod%d flag%d mi%d mymod%d\n,k,pre,phi,mod,flag,preflag*phi,ksm[k].mod);
// }return ksm[k].calc(preflag*phi)%mod;
}
inline int solve(int lim,int x,int mod){return Solve(1,lim,x,mod);
}
int top;
void calc(int k,int x){int phigetphi(x);w[k]phi;if(x1){topk;return;}ksm[k].init(c,x);calc(k1,phi);
}int a[N];
#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
int mn[N2],sum[N2];
inline void pushup(int k){mn[k]min(mn[ls],mn[rs]);sum[k](sum[ls]sum[rs])%mod;return;
}
void build(int k,int l,int r){if(lr){sum[k]a[l];return;}build(ls,l,mid);build(rs,mid1,r);pushup(k);
}
int ask(int k,int l,int r,int x,int y){if(xlry) return sum[k];int res(0);if(xmid) resask(ls,l,mid,x,y);if(ymid) resask(rs,mid1,r,x,y);res%mod;return res;
}
void change(int k,int l,int r,int x,int y){if(mn[k]top) return;if(lr){mn[k];sum[k]solve(mn[k],a[l],mod);//printf(k%d pos%d mn%d sum%d\n,k,l,mn[k],sum[k]);return;}if(xmid) change(ls,l,mid,x,y);if(ymid) change(rs,mid1,r,x,y);pushup(k);
}
void write(int x){if(x9) write(x/10);putchar(0x%10);
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();modread();cread();w[0]mod;calc(1,mod);//printf(top%d\n,top);//for(int i0;imod;i){// for(int j0;jtop;j) printf(x%d tim%d %lld\n,i,j,solve(j,i,mod));//}//return 0;for(int i1;in;i) a[i]read();build(1,1,n);for(int i1;im;i){int opread(),lread(),rread();//ok;if(op0) change(1,1,n,l,r);else{write(ask(1,1,n,l,r));putchar(\n);}}return 0;
}
/*
*/
