题目

Solution

1.容斥O(n的因子个数^2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,cnt,j,k;
ll ans,n,s[520],p[520];
ll pw(ll x,ll y){
    ll z=1;
    for (;y;y>>=1,x=x*x)
        if (y&1) z=z*x;
    return z;
}
int main(){
    scanf("%lld",&n);
    for (i=1;i*i<=n;i++)
        if (n%i==0) p[cnt++]=i;
    k=cnt*2-(p[cnt-1]*p[cnt-1]==n);
    for (i=0;i<cnt;i++) p[k-i-1]=n/p[i];
    for (i=k-1;i>=0;i--){
        s[i]=n/p[i];
        for (j=i+1;j<k;j++)
            if (p[j]%p[i]==0) s[i]-=s[j];
        ans+=p[i]*s[i];
    }
    printf("%lld",ans);
}

2.欧拉函数 O ( n 的 因 子 个 数 ∗ n 1 / 2 ) 或 O ( n 1 / 2 ) 或 O ( n 1 / 4 )

题解
我留下来慢慢看，毕竟我连Pollard_rho算法都没学过