欧拉函数

怕自己忘记

放道例题

201. 可见的点 - AcWing题库

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define double long double
 5 #define ull unsigned long long 
 6 #define QAQ 0
 7 const int N=1e5+1,inf=0x3f3f3f3f,mod=1e7+7;
 8 
 9 int n;
10 bool vis[N];
11 int prime[N],euler[N];
12 
13 void get_euler(int u)
14 {
15     euler[1]=1;//1是任何数的质数
16     int cnt=0;
17     for(int i=2;i<=n;i++)
18     {
19         if(!vis[i])
20         {
21             prime[cnt++]=i;
22             euler[i]=i-1;
23             
24         }
25         for(int j=0;prime[j]<=u/i;j++)
26         {
27             vis[i*prime[j]]=true;
28             if(i%prime[j]==0)
29             {
30                 euler[i*prime[j]]=prime[j]*euler[i];
31                 break;
32             }
33             euler[i*prime[j]]=euler[i]*(prime[j]-1);
34         }
35     }
36 }
37 
38 
39 void solve(int T)
40 {
41 
42     cin>>n;
43     get_euler(n);
44     int res=1;
45     for(int i=1;i<=n;i++)res+=euler[i]*2;
46     cout<<T<<' '<<n<<' '<<res<<'\n';
47 }
48 
49 
50 signed main()
51 {
52     std::ios::sync_with_stdio(false);
53     cin.tie(0),cout.tie(0);
54     int T;
55     cin>>T;
56     for(int i=1;i<=T;i++)solve(i);
57     return QAQ;
58 }