这两题其实是不一样的两道题。。
然而我还是想把他们放在一起。。
因为他们都用到了裴蜀定理

ORZ TKJ

其实我的辣鸡理解就是：几个数加加减减，最小的数就是他们的最大公倍数

然后这两题就好做了

前者用个线段树维护一下，根据更相减损术，差分以后加上原来的一个数的gcd就是序列的gcd
因为是差分，所以修改就是改两个数就好了

#include<cstdio>
#include<cstring>
const int N=100005;
int n,m;
int a[N];
struct qq {int l,r;int c;int s1,s2; }s[N*2];int num=0;
int f[N];//用树状数组差分维护原序列
int abs (int x){
   return x<0?-x:x;}
int gcd(int x,int y){
   return y==0?x:gcd(y,x%y);}
void bt (int l,int r)
{int aa=++num;s[aa].l=l;s[aa].r=r;if (l==r){s[aa].c=a[l]-a[l-1];return ;}int mid=(l+r)>>1;s[aa].s1=num+1;bt(l,mid);s[aa].s2=num+1;bt(mid+1,r);s[aa].c=gcd(s[s[aa].s2].c,s[s[aa].s1].c);
}
int lb (int x){
   return x&(-x);}
void add (int x,int y){
   while (x<=n){f[x]+=y;x+=lb(x);}}
int get (int x)
{int lalal=0;while (x>=1){lalal=lalal+f[x];x-=lb(x);}return lalal;
}
int Get(int now,int l,int r)
{if (l>r) return 0;if (s[now].l==l&&s[now].r==r)   return s[now].c;int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) return Get(s1,l,r);else if (l>mid) return Get(s2,l,r);else return gcd(Get(s1,l,mid),Get(s2,mid+1,r));
}
void change (int now,int x,int z)
{if (s[now].l==s[now].r){s[now].c+=z;return ;}int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (x<=mid) change(s1,x,z);else change(s2,x,z);s[now].c=gcd(s[s1].c,s[s2].c);
}
int main()
{scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)scanf("%d",&a[u]);bt(1,n);for (int u=1;u<=n;u++)add(u,a[u]-a[u-1]);while (m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if (op==1)printf("%d\n",abs(gcd(get(l),Get(1,l+1,r))));else{int x;scanf("%d",&x);add(l,x);change(1,l,x);if (r<n){add(r+1,-x);change(1,r+1,-x);}}}return 0;
}

然后后者就直接用map看一下那个因子出现了多少次，大于k次且最大就是答案了

#include<cstdio>
#include<map>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k;
map<int,int> a;
int main()
{scanf("%d%d",&n,&k);for (int u=1;u<=n;u++){int x;scanf("%d",&x);for (int i=1;i*i<=x;i++){if (x%i==0){a[i]++;if (i*i!=x)a[x/i]++;}}}for (map<int,int>::reverse_iterator it=a.rbegin();it!=a.rend();it++){if (it->second>=k){printf("%d",it->first);break;}}return 0;
}