网站外链代发,网站不备案访问,做网站推广需要具备哪些条件,中交建设设计院有限公司网站Problem - E - Codeforces 思路#xff1a;观察给定的函数#xff0c;其实就是求与这个数互质的数的个数#xff0c;即欧拉函数#xff0c;我们发现一个数迭代欧拉函数不会很多#xff0c;那么对于第一个操作来说我们可以直接暴力修改#xff0c;而对于第二个操作来说观察给定的函数其实就是求与这个数互质的数的个数即欧拉函数我们发现一个数迭代欧拉函数不会很多那么对于第一个操作来说我们可以直接暴力修改而对于第二个操作来说就是求l,r的最近公共祖先那么我们可以用线段树维护区间的最近公共祖先并且由于迭代的次数很少所以并不需要建图直接暴力跳跃求最近公共祖先即可那么最总的答案就是用l到r的深度之和-最近公共祖先的深度乘以区间长度这就是把这每个点跳跃到最近公共祖先的花费
一定不要建图建图会MLE
// Problem: E. Li Hua and Array
// Contest: Codeforces - Codeforces Round 864 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1797/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms#includebits/stdc.h
#includesstream
#includecassert
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
const double eps1e-7;
const int N5e67 ,M6e77, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} return x*f;}
inline void write(ll x) {if(x 0) {putchar(-); x -x;}if(x 10) write(x / 10);putchar(x % 10 0);}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen(in_put.txt,r,stdin);freopen(my_out_put.txt,w,stdout);}
bool cmp0(int a,int b) {return ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename T T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf(\n----------------------------------\n);}int T,hackT;
int n,m,k;
int cost[N];
int pr[3000],cnt;
bool st[3000];
int vis[N];
int depth[N];
struct Node{int l,r;int start;int sum;int add;
};
Node tr[N*4];int lca(int a,int b) {while(a!b) {if(ab) avis[a];else bvis[b];}return a;
}void pushup(int u) {tr[u].sumtr[u1].sumtr[u1|1].sum;tr[u].addtr[u1].addtr[u1|1].add;tr[u].startlca(tr[u1].start,tr[u1|1].start);
}void build(int u,int l,int r) {if(lr) {if(depth[cost[l]]0) tr[u]{l,r,cost[l],depth[cost[l]],1};else tr[u]{l,r,cost[l],depth[cost[l]],0};}else {tr[u]{l,r,INF,0,0};int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);}
}void modify(int u,int l,int r) {if(tr[u].r-tr[u].l1tr[u].add) return ;if(tr[u].ltr[u].r) {int tpvis[tr[u].start];if(depth[tp]0) tr[u]{tr[u].l,tr[u].r,tp,depth[tp],1};else tr[u]{tr[u].l,tr[u].r,tp,depth[tp],0}; }else {int midtr[u].ltr[u].r1;if(lmid) modify(u1,l,r);if(rmid) modify(u1|1,l,r);pushup(u);}
}int query_sum(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u].sum;else {int midtr[u].ltr[u].r1;int res0;if(lmid) resquery_sum(u1,l,r);if(rmid) resquery_sum(u1|1,l,r);return res;}
}int query_lca(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u].start;else {int midtr[u].ltr[u].r1;if(lmidrmid) {int aquery_lca(u1,l,r);int bquery_lca(u1|1,l,r);return lca(a,b);}else if(lmid) return query_lca(u1,l,r);else return query_lca(u1|1,l,r);}
}void get(int x) {int txx;int resx;for(int i0;icntpr[i]x/pr[i];i) {if(x%pr[i]0) {resres/pr[i]*(pr[i]-1);while(x%pr[i]0) x/pr[i];}}if(x!1) resres/x*(x-1);vis[tx]res;depth[tx]depth[res]1;
}void init() {int tsqrt(5000000);for(int i2;it;i) {if(!st[i]) pr[cnt]i;for(int j0;pr[j]t/i;j) {st[pr[j]*i]true;if(i%pr[j]0) break;}}depth[1]0;for(int i2;i5000000;i) get(i);
}void solve() {nread(),mread();for(int i1;in;i) cost[i]read();init();build(1,1,n);while(m--) {int opread();int lread(),rread();if(op1) {modify(1,l,r);}else if(op2) {int squery_lca(1,l,r);int sumquery_sum(1,l,r);printf(%d\n,sum-depth[s]*(r-l1));}}
} int main() {// init();// stin();// ios::sync_with_stdio(false); // scanf(%d,T);T1; while(T--) hackT,solve();return 0;
}
