[2020.12.08周二]欧拉表

[2020.12.08周二]欧拉表

Send a Table

题意：题面读起来异常离谱。简述一下：求小于n，的互质对个数。

题解：等价于求\(2*\sum_{i=1}^{n}\varphi(i) -1\),减一是因为（1，1）只应该被算一次。

#include
using namespace std;
const int maxn=5e4+5;
long long phi[maxn],sum[maxn];
void phi_table()
{
    memset(phi,0,sizeof(phi));
    phi[1]=1;sum[1]=1;
    for(int i=2;i