Description

给定一个正整数\(N(N\le2^{31}-1)\)

求

\[ans1=\sum_{i=1}^n \varphi(i)\]

\[ans_2=\sum_{i=1}^n \mu(i)\]

Solution

总算是写了一个不会\(TLE\)的杜教筛，不想用\(map\)，因此上了一个很丑的\(Hash\)……

Code

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 1900000int cnt,pr[MN];bool mark[MN];struct Node{int id;ll phi,mu;}MI[MN];inline void init(){    register int i,j;    for(i=1;i
     
       a[mod];        int ha,i;        Node em;    public:        Hash(){em=(Node){0,0ll,0ll};};        inline void insert(int id,ll phi,ll mu){a[id%mod].push_back((Node){id,phi,mu});}        inline Node find(int id)        {            ha=id%mod;            for(i=a[ha].size()-1;~i;--i) if(a[ha][i].id==id) return a[ha][i];            return em;        }}HA;inline Node calc(int n){    if(n
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！