前两篇题解筛素数完全就是画蛇添足啊……
本题答案就是 $$\sum_{d\mid n}\frac{n}{d}\varphi(d)$$ 就不再多说了。
刚开始打了个纯纯的暴力，结果给 T 了，然后看了看题解说要筛素数……于是也被误导了写了个筛素数的……结果最后才发现 T 的原因是溢出了……
A 了之后又仔细想了一下，其实直接算的话复杂度并不是 $O(n)$。
正确的复杂度是什么？考虑枚举 $n$ 的约数复杂度为 $O(\sqrt{n})$，而对于一个约数 $d$，计算其欧拉函数也就是枚举其质因子的复杂度也为 $O(\sqrt{d})$，于是其复杂度的计算式应为 $$\sum_{d|n}\sqrt{d}$$ 可以变换一下，得到 $$\sum_{d|\sqrt{n}} d$$二者虽不是完全等价，但是是同阶的，可以用来分析。于是发现这是一个约数和函数，即 $\sigma(\sqrt{n})$。在这篇文章中，根据引理二，暴力做法的复杂度更加精确的上界应该是 $O(\sqrt{n}\log\sqrt{n})$。考虑到 $n<2^{31}$，本题暴力完全可以通过。

//TLE不一定是因为复杂度高，
//有可能只是因为你忘了开long long ——鲁迅
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int phi(int x)
{
    int ans=x;
    for(int i=2;(ll)i*i<=x;++i)
        if(x%i==0)
        {
            ans=(ll)ans*(i-1)/i;
            while(x%i==0) x/=i;
        }
    if(x>1) ans=(ll)ans*(x-1)/x;
    return ans;
}

int main()
{
    int n; scanf("%d",&n);
    ll ans=0;
    for(int i=1;(ll)i*i<=n;++i)
        if(n%i==0)
        {
            ans+=(n/i)*phi(i);
            if(i*i!=n) ans+=i*phi(n/i);
        }
    printf("%lld",ans);
    return 0;
}

import java.io.*;

public class Main{
    static int N = 100010;
    static int[] p = new int[N];
    static int m;
    static int n;
    static int[] size = new int[N];
    static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        for(int i=1;i<=n;i++){
            p[i]=i;
            size[i]=1;
        }
        while(m-->0){
            String[] strs = br.readLine().split(" ");
            if(strs[0].equals("C")){
                int a = Integer.valueOf(strs[1]);
                int b = Integer.valueOf(strs[2]);
                if(find(a)!=find(b)){
                    size[find(b)]+=size[find(a)];//看好选B的祖宗作为根，只保留根节点的size
                    p[find(a)]=find(b);  
                } 
            }else if(strs[0].equals("Q1")){
                int a = Integer.valueOf(strs[1]);
                int b = Integer.valueOf(strs[2]);
                if(find(a)!=find(b))  System.out.println("No");
                else    System.out.println("Yes");
            }else{
                int a = Integer.valueOf(strs[1]);
                System.out.println(size[find(a)]);
            }
        }
    }
}

#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int primes[N],cnt;
int phi[N];
bool st[N];


LL getoula(int n)
{   
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=primes[j]*phi[i];
                break;
            }
            if(i%primes[j]!=0)
            {
                phi[primes[j]*i]=(primes[j]-1)*phi[i];

            }

        }
    }
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        res+=phi[i];
    }
    return res;
}


int main()
{

    int n;
    cin>>n;
    cout<<getoula(n)<<endl;


    return 0;
}

import java.io.*;

public class Main{
    static int N = 100010;
    static int[] p = new int[N];
    static int m;
    static int n;
    static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        for(int i=1;i<=n;i++){
            p[i]=i;
        }
        while(m-->0){
            String[] strs = br.readLine().split(" ");
            int a = Integer.valueOf(strs[1]);
            int b = Integer.valueOf(strs[2]);
            if(strs[0].equals("M")){
                p[find(a)]=find(b);
            }else{
                if(find(a)!=find(b))  System.out.println("No");
                else    System.out.println("Yes");
            }
        }
    }
}

#include<iostream>
#include<algorithm>

using namespace std;



int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        scanf("%d",&a);
        int res=a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                res=res/i*(i-1);
                while(a%i==0)a/=i;
            }
        }
        if(a>1)res=res/a*(a-1);
       printf("%d\n",res);   
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;


int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        auto t=gcd(a,b);
        printf("%d\n",t);
    }

    return 0;
}

概括：
1.由数据范围反推时间复杂度的选择算法，详细见y总分享
2.递归的三种题型：
{
1. 指数型：双分支
2. 全排列：多分支(不讲究顺序)
3. 组合型：多分枝（讲究顺序）
{
与全排列最关键的区别：有序
技巧：
人为升序，即新增的数字只能比上一个位置的数字要大，所以应设置一个参数为新增数字的最小起点。
}
}
3.带分数：说实话，第一遍自己敲还是不大看得懂，明天再敲多几次并且去csdn看多几钟解法。说实话原来自己在看题目的时候我也能想到全排列却唯独不知道应该怎么分割，
y总的视频里用的方法是: （a10+i. eg: 12变成123 可以用 1210+3）
3.1原理：
{
(1).全排列，枚举 a 的条件里枚举 c ,此时 b 成了由两个变量和一个常量表达的表达式。
(2).a是一定会小于n的，这是边界条件
}

3.2
memcpy的用法：
strcpy只可以用来复制字符串，但memcpy却可以复制多种数据类型。
{
(1)原型：void memcpy(void dest, const void *src,unsigned int count);
(2)功能：由src所指内存区域复制count个字节到dest所指内存区域。
(3)注意事项参考博客：https://blog.csdn.net/weixin_44717958/article/details/98490680
}

一开始没过 因为存在某个点的价值是0 数组又开不到-1 所以给价值整体加一 这样就不会出现娶不到的情况

C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
ll mod=1e9+7;
const int N =51;
ll dp[N][N][25][25];
int arr[N][N];
int n,m,k;
using namespace std;
void solve(int i,int j,int num,int val)
{
    if(dp[i][j][num][val]!=-1)
        return ;
    dp[i][j][num][val]=0;
    if(i==n&&j==m&&num==k)
    {
        dp[i][j][num][val]=1;
        return ;
    }
    if(arr[i][j]>val&&num<k)
    {
        solve(i,j,num+1,arr[i][j]);
        dp[i][j][num][val]+=dp[i][j][num+1][arr[i][j]];
        dp[i][j][num][val]%=mod;
    }
    if(i<n)
    {
        solve(i+1,j,num,val);
        dp[i][j][num][val]+=dp[i+1][j][num][val];
        dp[i][j][num][val]%=mod;
    }
    if(j<m)
    {
        solve(i,j+1,num,val);
        dp[i][j][num][val]+=dp[i][j+1][num][val];
        dp[i][j][num][val]%=mod;    
    }
}
int main()
{
    memset(dp,-1,sizeof dp);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>arr[i][j];
            arr[i][j]++;
        }
    solve(1,1,0,0);
    cout<<dp[1][1][0][0]%mod;   

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static long[] arr=new long[100100];
    static int p=131;
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String s[]=r.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int m=Integer.parseInt(s[1]);
        String ss[]=r.readLine().split(" ");
        String res=ss[0];


        for (int i = 1; i <=res.length() ; i++) {
            arr[i]=arr[i-1]*p+res.charAt(i-1);
        }
        while(m-->0){
            String line[]=r.readLine().split(" ");
            int l1=Integer.valueOf(line[0]);
            int r1=Integer.valueOf(line[1]);
            int l2=Integer.valueOf(line[2]);
            int r2=Integer.valueOf(line[3]);
            long res1=Jisuan(l1,r1);
            long res2=Jisuan(l2,r2);
            // System.out.println(res1+" "+res2);
            if(res1==res2)
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }
    public static long Jisuan(int x,int y){

            long tp=arr[x-1]*(long)(Math.pow(p,y-x+1));
            return arr[y]-tp;

    }
}

是因为数组long不行吗？

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
const int MOD=1e9+7;
typedef long long LL;


int main()
{
    int n;
    cin>>n;
    unordered_map<int,int>prime;
    while(n--)
    {
      int a;    
      scanf("%d",&a);    
      for(int i=2;i<=a/i;i++)            
      {
          while(a%i==0)
          {
              a/=i;
              prime[i]++;
          }
      }
      if(a>1)prime[a]++;
    }
    LL res=1;
    for(auto pr:prime)
    {
        int x=pr.first,b=pr.second;
        LL t=1;
        while(b--)
        {
            t=(x*t+1)%MOD;
        }
        res=(res*t)%MOD;
    }
    cout<<res<<endl;
    return 0;
}