济南百度网站开发,使用php如何做购物网站,网站的基本组成部分有哪些内容,期货交易软件定制开发解析
大降智题。 受相逢是问候的影响#xff0c;第一眼直接线段树#xff0c;写完WA完才发现这个玩意没有结合律。 然后开始用 xyz(xy)yz−1x^{y^z}(x^y)^{y^{z-1}}xyz(xy)yz−1 这样的东西嗯做#xff0c;结果只是在玩泥巴。 lemma#xff1a;迭代求 φ\varphiφ 的次数是…解析
大降智题。 受相逢是问候的影响第一眼直接线段树写完WA完才发现这个玩意没有结合律。 然后开始用 xyz(xy)yz−1x^{y^z}(x^y)^{y^{z-1}}xyz(xy)yz−1 这样的东西嗯做结果只是在玩泥巴。 lemma迭代求 φ\varphiφ 的次数是 log 级别的。 证明偶数的 φ\varphiφ 至少折半对于 n2n2n2φ(n)\varphi(n)φ(n) 恒为偶数因为 gcd(i,n)gcd(n−i,n)\gcd(i,n)gcd(n-i,n)gcd(i,n)gcd(n−i,n)。
所以直接暴力往后扫模数为1就返回就可以了。
//luogu
#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 N1e5100;
//const int mod998244353;
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;
}#define pr pairll,bool
#define mkp make_pair
inline pr ksm(ll x,ll k,int mod){ll res(1);bool flag0; while(k){if(k1){resres*x;if(resmod){res%mod;flag1;}}xx*x;if(xmodk1){x%mod;flag1;}k1;}return mkp(res,flag);
}mapint,intmp;
int n,m;
int w[N];inline int getphi(int x){if(mp.count(x)) return mp[x];int orix;int wsqrt(x),resx;for(int i2;iw;i){if(x%i0){res1ll*res*(i-1)/i;while(x%i0) x/i;}}if(x1) res1ll*res*(x-1)/x;return mp[ori]res;
}pr calc(int l,int r,int mod){if(lr){return mkp(w[l]%mod,w[l]mod);}if(mod1) return mkp(0,1);int phigetphi(mod);pr ocalc(l1,r,phi);return ksm(w[l],o.firsto.second*phi,mod);
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();int modread();for(int i1;in;i) w[i]read();mread();for(int i1;im;i){int lread(),rread();printf(%lld\n,calc(l,r,mod).first);}return 0;
}
/**/
