此篇属于CodeForces比赛题解集合链接

补题链接 https://codeforces.com/gym/104128
如何评价2022icpc南京站 https://www.zhihu.com/question/572113636

因为本人很菜，今天先补题补到银牌(5题)水平吧

进度(3/13)

I Perfect Palindrome

知识点:回文的性质

猜:将所有元素变成相同字母的代价。如何证明？
循环转还要每次转完都是回文的，可以知道，所有字母都要对应相同。

#include<bits/stdc++.h>

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  //#endif
}


void solve()
{
     string x; cin >> x; int len = x.size();
     map<int,int> mp; int res = 0;
     for(int i = 0;i < len;i ++) mp[x[i] - 'a'] ++;
     for(auto k : mp) res = max(res,k.second);
     res = len - res;
     cout << res << endl;
}

int main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 0; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

A Stop, Yesterday Please No More

知识点:逆操作,矩阵,二维差分

首先考虑没有洞的情况。
考虑逆操作，维护边界到达过的最值。最后可以得到没有洞的情况下，剩下的老鼠矩阵。

然后考虑有洞的情况。
这个时候我们只关心剩下的老鼠矩阵在哪些位置停留过。
每次移动，考虑剩下的老鼠矩阵。
枚举左上端点，如果没有重合，说明每一个老鼠和每一个位置都没有对应重合过。
考虑二维查分，维护一下每个位置到达过的老鼠数量。

最后统计格子上数量等于剩下老鼠数量减去要求剩下的老鼠数量的格子数量即可。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  //#endif
}

const int N = 1e3 + 10;

int n,m,k;
int l,r,u,d;
int lnow,rnow,unow,dnow;
bool st[N][N];
int mp[N][N];
int res;


void pr()
{
  cout << u << ' ' << d << ' ' << l << ' ' << r << endl;  
}

void init()
{ 
  l = lnow = u = unow = 1;
  r = rnow = m;
  d = dnow = n;
  memset(st,false,sizeof st);
  memset(mp,0,sizeof mp);
  res = 0;
}

void add(int x,int y,int p,int q)
{
  if(st[x][y]) return; st[x][y] = true;
  mp[x][y] ++, mp[p+1][y] --, mp[x][q+1] --, mp[p+1][q+1] ++;
}

void solve()
{
  cin >> n >> m >> k;
  string s;cin >> s;

  init();

  for(int i = 0;i < s.size();i ++)
  {
     if(s[i] == 'U') dnow --, unow--,d = min(d,dnow);
     if(s[i] == 'D') dnow ++, unow++,u = max(u,unow);
     if(s[i] == 'L') lnow ++, rnow++,l = max(l,lnow);
     if(s[i] == 'R') lnow --, rnow--,r = min(r,rnow);
  }
 // pr();
  if(u > d || l > r){
    if(k == 0) cout << n*m << '\n';
    else cout << "0" << endl;
    return;
  }
  int delta = (d - u + 1) * (r - l + 1) - k;

  add(u,l,d,r);
  for(int i = 0;i < s.size();i ++)
  {
     if(s[i] == 'U') u ++,d++;
     if(s[i] == 'D') u --,d--;
     if(s[i] == 'L') l --,r--;
     if(s[i] == 'R') l ++,r++;
     add(u,l,d,r);
  }
  for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) 
  mp[i][j] += (mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1]);
  for(int i = 1; i <= n;i ++) for(int j = 1; j <= m;j ++)
  if(mp[i][j] == delta) res ++;
  cout << res << endl;
}

int main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 0; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

G Inscryption

知识点: 模拟,贪心,反悔,数学

一开始，我没有想到顺序关系，wa了2发。
后来发现，这题和顺序关系很大，必须按顺序贪心模拟。

#include <bits/stdc++.h>
using namespace std;


int n;

void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  //#endif
}

inline int gcd(int a,int b) 
{    
    while(b^=a^=b^=a%=b);    
    return a;
}

void solve() {
    scanf("%d", &n);

    int s = 1, c = 1, t = 0;
    bool failed = false;

    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);

        if (x == 1) s++, c++;

        else if (x == -1) {

            if (c > 1) c--;

            else if (t >= 1) t--, s++, c++;

            else failed = true;
        } else {

            if (c > 1) t++, c--;
            else s++, c++;
        }
    }
    if (failed) printf("-1\n");
    else {
        int g = gcd(s, c);
        printf("%d %d\n", s / g, c / g);
    }
}

int main() {
    //fileio();
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

知乎评价

最后1个队11题，5个队9题，7个队8题，14个队7题，41个队6题，32个队5题，62个队4题，105个队3题，140个队2题，57个队1题。铜线如同预测是3题，银线是5题加上10个4题（其实原本期望能完全收入5题线的），金牌是7题加上10个6题（同样也是期望能完全收入7题线）。冠亚季原本期望至少有一个10题，结果被逆十字打出了n+2，而且HL都无人通过。感觉主要还是这次比赛大家收到的debuff太强了，稍微和预测有一些偏差。

作者：陈靖邦
链接：https://www.zhihu.com/question/572113636/answer/2800844540
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

此篇属于CodeForces比赛题解集合链接

比赛地址
https://codeforces.com/contest/1825

cn场 洛天依哇哇哇

补题！今天补完！

A

找最大的不是回文串的子串长度。
一想，只可能是len - 1 或者 -1

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;
int T;


string s;

void solve()
{
   cin >> s;
   bool f = false;
   for(int i = 0;i < s.size();i ++)
   if(s[i] != s[0]) f = true;
   if(!f) {cout << "-1" << endl;return;}
   int len = s.size(); cout << len - 1 << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  T = 1;
  cin >> T;
  while(T--)
  solve();
}

B

统计所有以（zero point）为起点的子矩阵 中 最大值与最小值的差 的sum。

我们只需要找到最大的 delta 和 第二大的 delta 放在开头 贪一下就出来了。

具体看代码。

咕咕咕咕

#include<bits/stdc++.h>
#define int long long

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}

int n,m;
const int N = 1e4 + 10;
int a[N];
void solve()
{
   cin >> n >> m; int len = n * m;
   for(int i = 0;i < len;i ++) cin >>a[i]; sort(a, a + len);
   int maxdel = a[len - 1] - a[0];
   int semaxdel = 0; //int zeropoint = 0;
   if(a[len - 2] - a[0] < a[len - 1] - a[1]) semaxdel = a[len-1] - a[1];
   else semaxdel = a[len-2] - a[0];
   int cntf = 0; int cnts = 0;
   if((n-1)*m < (m-1)*n) cntf = (m-1)*n, cnts = n-1;
   else cntf = (n-1)*m, cnts = m-1;
   cout << maxdel*cntf + semaxdel * cnts << endl;
   return;
}

signed main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

C

第一种坐法 坐在最左的人的左边，没有人就坐在最右边
第二种坐法 坐在最右的人的右边，没有人就坐在最左边
第三种坐法 直接坐在 xi 位置上

你可以调整人的入场顺序，尽量让最多的人入座

我们会发现，第一个人很关键。
第一个人如果是第一种坐法，第二种就没法坐了。反之也对。

我们枚举第一个人是上面的三种坐法。

其中第三种坐法需要更深入的讨论。

第三种的讨论使用差分数组，左右差分一下就好。

咕咕咕咕，看代码，不懂的可以私我。

#include<bits/stdc++.h>
#define int long long
#define debug cout << "debug" << endl

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}

int n,m;
const int N = 1e5 + 10;
int l[N],r[N];
int logs[N];

void pr()
{
    for(int i = 1;i <= m;i ++) cout << l[i] << ' '; cout << endl;
    for(int i = 1;i <= m;i ++) cout << r[i] << ' '; cout << endl;
}

void solve()
{
    //debug;
    cin >> n >> m; 
    for(int i = 0;i < m + 5;i ++) l[i] = r[i] = logs[i] = 0; 
    l[0] = -1; r[m+1] = -1;
    int lcnt = 0; int rcnt = 0;int midcnt = 0;int res = 0;
    set<int> pos;// pr();
   for(int i = 0;i < n;i ++)
   {
     int x; cin >> x;
     if(x == -1) lcnt ++;
     if(x == -2) rcnt ++;
     if(x > 0) pos.insert(x), logs[x] = -1;
   }
   midcnt = pos.size();
  // pr();
   for(int i = 1;i <= m;i ++) l[i] += (l[i-1] + 1 + logs[i-1]);
   for(int i = m;i >= 1;i --) r[i] += (r[i+1] + 1 + logs[i+1]);  //pr();
   for(int i : pos){

        int lres = min(lcnt,l[i]); int rres = min(rcnt,r[i]);
        res = max(res, lres + rres + midcnt);
        //cout << i << " ** " << res << endl;
   } 
    res = max(res,lcnt + midcnt); res = max(res, rcnt + midcnt);
    res = min(res,m);
    cout << res  << endl;
}

signed main()
{
    //fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

D1

题意看的有点懵。

有n个岛，连成一棵树，选了k个岛屿。取遍所有k个岛屿的情况。

对于每个情况，再取遍 n 个岛屿，对于每个岛屿，计算距离k个岛屿的距离和。

每个情况下， 好岛就是距离和最小的岛屿。

求平均每个情况有多少好岛？ 然后moudle 一下。

懵！一脸懵b

好在 k 只有 1 2 3 这几种情况

k == 1 的话 每种情况，好岛就是自己 所以答案是1
k == 3 的话 在树上选的那三个岛 一定能找出一条链来，然后可以证明 好岛就是中间那个岛。
k == 2 怎么办？ 不会，寄
但我好像有懂了： k == 2 的话，直接将两个点连起来，路上的所有的岛都是好岛。
ok，那怎么求全部的好岛？

那么我们反过来，对于给定一个岛，它是好岛的情况有多少？就是要在树上枚举经过它的区间。

这个区间要经过这个岛，一想，我去，就是这个岛是根结点，然后它的所有子树的大小 siz(i) 乘起来

然后一看，要枚举每个点为顶点，再扫一遍，n方，寄

看看题解，这个dfs，绝杀哇，直接解决这个问题，绝杀，还有这个公式，稍微推一下，绝杀

#include<bits/stdc++.h>
#define int long long

using namespace std;
void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}
const int mod = 1e9 + 7;

int quick_pow(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b&1) res = res % mod * a % mod;
        a = a % mod * a % mod, b >>= 1;
    }
    return res;
}

const int N = 2e5 + 10;

vector<int> g[N];
int n,k;
int siz[N],w[N];

void dfs(int u,int fa)
{
    siz[u] = 1;
    for(int i : g[u])
    {
        if(i != fa){
            dfs(i, u);
            siz[u] += siz[i];
            w[u] += siz[i]*siz[i]%mod;
            w[u] %= mod;
        }
    }
     (w[u]+=(n-siz[u])*(n-siz[u])%mod)%=mod; //  逆根方向 // 绝杀
}

void solve()
{
   cin >> n >> k;
   for(int i = 1;i < n;i ++){
    int u,v; cin >> u >> v; g[u].push_back(v);g[v].push_back(u);
   }
   if(k & 1){ cout << 1 << endl; return;}
   dfs(1,0); int res = 0;
   for(int i = 1;i <= n;i ++)
   {
      res += (((n-1)*(n-1)%mod-w[i]+mod)%mod)*quick_pow(2,mod-2)%mod;
      res %= mod;
   }
   cout << (res%mod*quick_pow(n*(n-1)/2%mod,mod-2)%mod + 2)%mod << endl;

}

signed main()
{
    fileio();
    ios::sync_with_stdio(false);
      cin.tie(0);
    int tc = 1; //cin >> tc;
    for(int i = 0;i < tc;i ++)solve();
}

此篇属于比赛题解集合(CF && AcWing Race)链接

比赛地址
https://codeforces.com/contest/1822

考试过了 abcd

后来补了efg

思路先咕咕咕，先考试期中，传个代码

A

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;
int T;

const int N = 200;
int a[N];
int b[N];
vector<int>tmp;

void solve()
{
  int n,m;
  cin >> n >> m;
  tmp.clear();
  for(int i = 1;i <= n;i ++)
  {
    cin >> a[i];a[i] += i-1;
    if(a[i] <= m) tmp.push_back(i);
  }
  int resid = 0;
  int res = 0;
  for(int i = 1;i<= n;i ++) cin >> b[i];
  if(tmp.size())
  {
    for(auto t:tmp)
    { 
      if(res < b[t])
      {
        resid = t;
        res = b[t];
      }
    }
    cout << resid << endl;
  }
  else cout << -1 << endl;

}

int main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

B

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define int long long

const int INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
const int N = 2e5 + 10;
int T;
int n;
int a[N];
int cnt = 0;
int maxxx;
void solve2()
{
    sort(a + 1, a + n + 1);
        if (a[1] < 0 && a[2] < 0)
        {
            maxxx = max(a[1] * a[2], maxxx);
        }
        if (a[n] > 0 && a[n - 1] > 0)
        {
            maxxx = max(a[n] * a[n - 1], maxxx);
        }
        if (cnt)
        {
            maxxx = max(maxxx,0ll);
        }
    maxxx = max(maxxx, a[1] * a[2]);
    maxxx = max(maxxx, a[n] * a[n - 1]);

}
void solve()
{
     cin >> n;
         maxxx= -INF;
     cnt = 0;

        for (int i = 1; i <= n; i ++ ) 
        {
            cin >> a[i];
            if (!a[i]) cnt ++ ;
        }
        if (cnt == n || cnt == n - 1)
        {
            cout << 0 << endl;
            return;
        }
        solve2();
        cout << maxxx << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

C

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long

using namespace std;
int T;

int a;
void solve()
{
    cin >> a;
        a = a - 3;
        cout << 9 * a + a * (a - 1) + 17 << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

D

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;

const int N = 2e5 + 10;
int T;
int n;
int a[N];


void solve()
{
   cin >> n;
   if(n == 1)
   {
    cout << 1 << endl;
    return;
   }
   if(n%2)
   {
    cout << -1 << endl;
    return;
   }
   a[0] = n;a[n/2]=n/2;
   int x = 1;
   for(int i = 1;i < n/2;i ++)
   {
      if(x)
      {
      a[i] = n - i;
      a[n-i] = i;
      }
      else
     {
        a[i] = i;
        a[n-i] = n - i;
      }
      x ^= 1;
   }
   for(int i = 0;i < n;i ++) cout << a[i] << ' ';
   cout << endl;

}

int main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

E

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define int long long
#define pb push_back

using namespace std;
const int N = 2e5 + 10;
int T;
int cnt[30];
int single_cnt[30];
bool used[30];
vector<int> id;
string x;

void init()
{
  id.clear();
  memset(used,false,sizeof used);
  memset(cnt,0,sizeof cnt);
  memset(single_cnt,0,sizeof single_cnt);
}

void pr()
{
  for(int i = 0;i < 26;i ++)
  cout << cnt[i] << ' ';
  cout << endl;
}

void solve()
{
    init();

    int n;cin >> n;
    cin >> x;
    if(n % 2) 
    {
      cout << -1 << endl;
      return;
    }

    for(int i = 0;i < n/2;i ++)
    {
      single_cnt[x[i]-'a'] ++;
      single_cnt[x[n - i - 1]-'a']++;
      if(x[i] == x[n - i - 1])
      {
        int ch = x[i] - 'a';
        if(!used[ch])
        id.pb(ch),used[ch] = true;
        cnt[ch]++;
      }
    }

    //pr();

    for(int i = 0;i < 26;i ++)
    if(single_cnt[i] > n/2) 
    {
      cout << -1 << endl;
      return;
    }

    int sum = 0;int res = 0;
    //pr();
    //cout << "id ";
    //for(int t : id)
    //cout << t << ' ';
    //cout << endl;
    for(int t : id) sum += cnt[t]; int odd = sum%2;
    for(int t : id) 
    {
      if(cnt[t] > sum/2)
      {
        res += sum/2;
        res += cnt[t] - sum/2;
        cout << res << endl;
        return;
      }
    }
     res += sum/2 + odd;
     cout << res << endl;


}

signed main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

F

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>

using namespace std;

using LL = long long;
int T;


void solve()
{
   int n,k,c;
   cin >> n >> k >> c;
   vector<vector<int> >g(n);
   for(int i = 0;i < n - 1;i ++)
   {
    int a,b;cin >> a >> b;a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
   }

   auto bfs = [&](int st)
   {
      vector<int> d(n,-1);
      queue<int> q;
      d[st] = 0;
      q.push(st);
      while(!q.empty())
      {
        int t = q.front();q.pop();
        for(auto j : g[t])
        {
          if(d[j] == -1)
          {
            d[j] = d[t] + 1;
            q.push(j);
          }
        }
      }
      return d;
   };

   auto d1 = bfs(0);
   int p = max_element(d1.begin(),d1.end()) - d1.begin();
   auto d2 = bfs(p);
   int q = max_element(d2.begin(),d2.end()) - d2.begin();
   auto d3 = bfs(q);

  LL res = 0;
  for(int i = 0;i < n;i ++)
  res = max(res,1LL * k * max(d2[i],d3[i]) - 1ll * c * d1[i]);
  cout << res << endl;

}

int main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

G

思路代码来自cup神

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
using LL = long long;

vector<int> go_fac(int n){ 
    vector<int> f;
    for(int i = 1; i * i <= n; i++){
        if (n % i == 0){
            f.push_back(i);
            if (i * i != n) f.push_back(n / i);
        }
    }
    return f;
}


int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int uplimit = 1e9;
    const int S = 1e6;

    auto C3 = [&](int x){
        return 1LL * x * (x - 1) * (x - 2);
    };

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        map<int, int> mp;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            mp[x] += 1;
        }
        LL ans = 0;
        for(auto &[x, y] : mp){
            ans += C3(y);
            if (x >= S){
                for(int j = 2; 1LL * j * x <= uplimit; j++){
                    if (x % j == 0 && mp.count(x * j) && mp.count(x / j)){
                        ans += 1LL * y * mp[x * j] * mp[x / j];
                    }
                }
            }
            else{
                auto f = go_fac(x);
                sort(f.begin(), f.end());
                for(auto u : f){
                    if (u == 1) continue;
                    if (1LL * x * u > uplimit) break;
                    if (mp.count(x / u) && mp.count(x * u)){
                        ans += 1LL * y * mp[x / u] * mp[x * u];
                    }
                }
            }
        }
        cout << ans << '\n';
    }

}

20230419

#include<bits/stdc++.h>
#define fi first
#define se second
#define log2(a) log(n)/log(2)
#define show(a) cout << a << endl;
#define show2(a,b) cout << a << ' ' << b << endl;
#define show3(a,b,c) cout << a << ' ' << b << ' ' << c << endl;
#define int long long

using namespace std;

void fileio()
{
  //#ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  //#endif
}

void fileclose()
{
    fclose(stdin);//关闭文件
    fclose(stdout);//关闭文件
}

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}

int T;


void solve()
{
   int a,b;
   cin >> a >> b;
   cout<< a + b << endl;
}

signed main()
{ 
    fileio();
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);T = 1;
    //cin >> T;
    while(T --) solve();
    fileclose();
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>

using namespace std;
int T;

const int N = 2e5 + 10;

int a[N];
int p[N];
int n,m;

void solve()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }

    priority_queue<int> pos;
    long long t = 0; 
    int ans = 0;

    for (int i = m; i >= 1; i--)
    {
        if (p[i] + t < p[m])
        {
            while (p[i] + t < p[m])
            {
                t += 2ll * pos.top();
                pos.pop();
                ans++;
            }
        }

        if (a[i] > 0)
            pos.push(a[i]);
    }

    priority_queue<int, vector<int>, greater<>> neg;
    t = 0;

    for (int i = m + 1; i <= n; i++)
    {
        if (a[i] < 0)
            neg.push(a[i]);

        if (p[i] - t < p[m])
        {
            while (p[i] - t < p[m])
            {
                t += 2ll * neg.top();
                neg.pop();
                ans++;
            }
        }
    }

    cout << ans << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while(T--)
      solve();
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<array>

using namespace std;
typedef long long ll;
int T;
const int M = 5e6 + 200;
const int N = 1e5 + 200;

int tot;
int dfn[M],dep[M],idx[M],ar[N];
ll phi[M],prime[M];
bool is_prime[M];
const ll inf = 0x3f3f3f3f3f3f3f3f;

vector<int>r[M];

void phi_table()
{
  memset(is_prime,true,sizeof is_prime);
  int cnt = 0;
  is_prime[1] = false;
  phi[1] = 1;
  int n = 5e6;
  for(int i = 2;i <= n;i ++)
  {
    if(is_prime[i])
    {
      prime[++ cnt] = i;
      phi[i] = i - 1;
    }
    for(int j = 1;j <= cnt && i * prime[j] <= n;j ++)
    {
      is_prime[i * prime[j]] = false;
      if(i % prime[j])
      {
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      }
      else
      {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  } 
}

struct node
{
  ll lca,depsum,cnt;
  bool isallone;
}tree[N*4];

int getlca(int x,int y)
{
  if(dep[x] < dep[y]) swap(x,y);

  while(dep[x] > dep[y])
    x = phi[x];

  if(x == y)
  return x;

  while(x != y)
  {
      x = phi[x];
      y = phi[y];
  }
  return x;
}

void dfs(int x)
{
  dfn[x] = ++ tot;
  idx[tot] = x;
  if(x != -1)
    dep[x] = dep[phi[x]] + 1; // 距离1的深度
  else dep[x] = 1;            // 边界
  for(auto v:r[x])
  dfs(v);
}
void update(int x)
{
  tree[x].lca = getlca(tree[x << 1].lca,tree[x << 1 | 1].lca);
  tree[x].depsum = tree[x << 1].depsum + tree[x << 1 | 1].depsum;
  tree[x].cnt = tree[x << 1].cnt + tree[x << 1 | 1].cnt;
  if(tree[x << 1].isallone && tree[x << 1 | 1].isallone)
  tree[x].isallone = true;
}

void build(int l,int r,int x)
{
  if(l == r)
    {
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r)>>1;
    build(l,      mid,x << 1);
    build(mid + 1,r  ,x << 1 | 1);
    update(x);
}

void modify(int l,int r,int x,int L,int R)
{// 当前区间左右边界 当前区间id 修改目标区间左右边界
  if(r < L || l > R) return;
  if(tree[x].isallone) return;

  if(l == r) // 单点修改
  {
    ar[l] == phi[ar[l]];
    if(ar[l] == 1) tree[x] = {ar[l],dep[ar[l]],1,1};//全1
    else tree[x] = {ar[l],dep[ar[l]],1,0};
    return;
  }
  int mid = l+r>>1;
  modify(l,     mid,x << 1    ,L,R);
  modify(mid + 1,r, x << 1 | 1,L,R);
  update(x);
}

array<ll,3> query(int l,int r,int x,int L,int R)
{// 当前索引到的查询区间左右端点 索引号 查询目标左右边界
  if(L <= l && R >= r)
  return {tree[x].lca,tree[x].depsum,tree[x].cnt};
  int mid = l+r>>1;
  if(R <= mid) return query(l,mid,x << 1,L,R);
  else
  {
    if(L > mid) return query(mid + 1,r,x << 1|1,L,R);
  else{
  array<ll,3>tp1 = query(l,mid,x << 1,L,mid);
  array<ll,3>tp2 = query(mid+1,r,x << 1|1,mid + 1,R);
  return {getlca(tp1[0],tp2[0]),tp1[1] + tp2[1],tp1[2] + tp2[2]};
  }
  }
}

void solve()
{
   int n,m;
   cin >> n >> m;
   phi_table();
   for(int i = 2;i <= 5e6;i ++)
   r[phi[i]].push_back(i);
   dfs(1);
   for(int i = 1;i <= n;i ++)
   cin >> ar[i];
   build(1,n,1);
   while(m --)
   {
    int opr,l,r;
    cin >> opr >> l >> r;
    if(opr == 2)
    {
      array<ll,3>res = query(1,n,1,l,r);
      ll ans = res[1] - res[2]*(dep[res[0]]*1ll);
      cout << ans << endl;
    }
    else modify(1,n,1,l,r);
   }
}

int main()
{
  //scanf("%d",&T);
  T = 1;
  while(T--)
      solve();
}

#include<bits/stdc++.h>
using namespace std;
#define MX 5000000 + 200
#define N 100000 + 200
int tot;
int dfn[MX],dep[MX],idx[MX],ar[N];
long long phi[MX],prime[MX];
bool is_prime[MX];
const long long inf = 0x3f3f3f3f3f3f3f3f;
vector<int>r[MX];
void phi_table() 
{
    memset(is_prime, 1, sizeof(is_prime));
    int cnt = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    int n = 5000000;
    for (int i = 2; i <= n; i++) 
    {
        if (is_prime[i]) 
        {
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) 
        {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else 
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}
struct node
{
    long long lca,depsum,cnt;
    bool isallone;

}tree[4 * N];
int getlca(int x,int y)
{
    if(dep[x] < dep[y])
        swap(x,y);
    while(dep[x] > dep[y])
        x = phi[x];
    if(x == y)
        return x;
    while(x != y)
        x = phi[x],y = phi[y];
    return x;
}
void dfs(int x)
{
    dfn[x] = ++ tot;
    idx[tot] = x;
    if(x != 1)
        dep[x] = dep[phi[x]] + 1;
    else
        dep[x] = 1;
    for(auto v:r[x])
        dfs(v);
}
void update(int x)
{
    tree[x].lca = getlca(tree[2 * x].lca,tree[2 * x + 1].lca);
    tree[x].depsum = tree[2 * x].depsum + tree[2 * x + 1].depsum;
    tree[x].cnt = tree[2 * x].cnt + tree[2 * x + 1].cnt;
    if(tree[2 * x].isallone && tree[2 * x + 1].isallone)
        tree[x].isallone = 1;
}
void build(int l,int r,int x)
{
    if(l == r)
    {
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,2 * x),build(mid + 1,r,2 * x + 1);
    update(x);
}
void modify(int l,int r,int x,int L,int R)
{
    if(r < L || l > R)
        return;
    if(tree[x].isallone)
        return;
    if(l == r)
    {
        ar[l] = phi[ar[l]];
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r) / 2;
    modify(l,mid,2 * x,L,R),modify(mid + 1,r,2 * x + 1,L,R);
    update(x);
}
array<long long,3>query(int l,int r,int x,int L,int R)
{
    if(L <= l && R >= r)
        return {tree[x].lca,tree[x].depsum,tree[x].cnt};
    int mid = (l + r) / 2;

    if(R <= mid)
        return query(l,mid,2 * x,L,R);
    else
    {
        if(L > mid)
            return query(mid + 1,r,2 * x + 1,L,R);
        else
        {
            array<long long,3>tmp1 = query(l,mid,2 * x,L,mid);
            array<long long,3>tmp2 = query(mid + 1,r,2 * x + 1,mid + 1,R);
            return {getlca(tmp1[0],tmp2[0]),tmp1[1] + tmp2[1],tmp1[2] + tmp2[2]};
        }
    }
}
int main()
{

    int n,m;
    scanf("%d %d",&n,&m);
    phi_table();
    for(int i = 2;i <= 5000000;i ++)
        r[phi[i]].push_back(i);
    dfs(1);
    for(int i= 1;i <= n;i ++)
        scanf("%d",&ar[i]);
    build(1,n,1);

    for(int i = 1;i <= m;i ++)
    {

        int opr,l,r;
        scanf("%d %d %d",&opr,&l,&r);
        if(opr == 2)
        {
            array<long long,3>res = query(1,n,1,l,r);
            long long ans = res[1] - res[2] * (dep[res[0]] * 1ll);
            printf("%lld\n",ans);
        }
        else
            modify(1,n,1,l,r);

    }

}