AC代码
```
#include <bits/stdc++.h>
using namespace std;
#define x = a x(a)
#define re register
const int maxn = 1e7 + 10;
int read()
{
int s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
bitset<(int)1e7+5>vis;
int prime[maxn], cnt;
int N;
inline void euler()
{
for(re int i=2;i<=N;++i)
{
if(!vis[i])
{
prime[++cnt]=i;
for(re int j=i;i<=N/j;++j)vis[i*j]=1;
}
}
}
unsigned long long f[maxn];
inline void sovle()
{
long long tmp=0;
for (re int k = N; k >= 1; k--)
{
tmp=(N / k);
f[k] = tmp * tmp;
for (re long long i = (k<<1) ; i <= N; i += k)
{
f[k] -= f[i];
}
}
}
int main()
{
N = read();
sovle();
euler();
unsigned long long ans = 0;
for (re int i = 1; i <= cnt; ++i)
{
ans += f[prime[i]];
}
cout << ans << endl;
return 0;
}
```
by dlydly @ 2022-07-14 15:56:44
> sovle
by TernaryTree @ 2022-07-14 15:57:09
@[Slytherin_always](/user/386921) ？？
by LiaoYF @ 2022-07-14 16:09:29
@[Slytherin_always](/user/386921) 是请求加强，不是tlqtj，只是发一下水代码
by LiaoYF @ 2022-07-14 16:10:07
@[Slytherin_always](/user/386921) 哪来的贵物
by 断清秋 @ 2022-07-14 16:11:44
@[Slytherin_always](/user/386921) 你懂不懂什么是tlqtj，不懂别在这《伸张正义》
by hank0402 @ 2022-07-14 16:14:53
2楼代码仅作为证明复杂度的依据，并无它意，相信针对性语言已经够强，还望阅读后做出评论
by dlydly @ 2022-07-14 16:14:59
快读快写+bitset优化都上了，卡常卡过去的你加强什么。
哦，这优化是我写的啊，那没事了。
by Rnfmabj @ 2022-07-14 16:47:13
```
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
int prime[maxn], cnt;
bool vis[maxn];
int N;
void euler()
{
for (int i = 2; i <= N; ++i)
{
if (!vis[i])
{
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= N; ++j)
{
vis[i * prime[j]] = 1;
if (!(i % prime[j]))
break;
}
}
return;
}
unsigned long long f[maxn];
void eee()
{
long long tmp = 0;
for (int k = N; k >= 1; k--)
{
tmp = (N / k);
f[k] = tmp * tmp;
for (long long i = k*2; i <= N; i += k)
{
f[k] -= f[i];
}
}
}
int main()
{
cin>>N;
eee();
euler();
unsigned long long ans = 0;
for (int i = 1; i <= cnt; ++i)
{
ans += f[prime[i]];
}
cout << ans << endl;
return 0;
}
```
如君所言，去了皮
800ms跑的飞快
by dlydly @ 2022-07-14 16:49:04
@[dlydly](/user/124786) 我所有点加起来都没800ms，飞快这词不是你这么用的
然后你又要开始“顺从”了是吧
by Rnfmabj @ 2022-07-14 16:53:56