杜教筛

专题练习 初等数论 杜教筛

---

---

Problem List

• 51Nod 1244 - 莫比乌斯函数之和
• 51Nod 1239 - 欧拉函数之和
• BZOJ 3944 - Sum
• HDU 5608 - function
• 51Nod 1238 - 最小公倍数之和 V3
• 51Nod 1237 - 最大公约数之和 V3
• 51Nod 1227 - 平均最小公倍数
• Tsinsen A1231 - Crash的数字表格
• SPOJ DIVCNT2 - Counting Divisors (square)
• 51Nod 1222 - 最小公倍数计数（复杂度分析）
• BZOJ 4176 - Lucas的数论
• 51Nod 1220 - 约数之和
• 51Nod 1584 - 加权约数和
• ZOJ 3881 - From the ABC conjecture（不需要使用正文方法）
• BZOJ 3512 - DZY Loves Math IV
• ZOJ 5340 - The Sum of Unitary
• Totient（常规积性函数求和，数据组数较多，只可分段打表）
• SPOJ DIVCNT3 - Counting Divisors
• (cube)（常规积性函数求和，注意代码长度限制，不可打表）
• 51Nod 1575 - Gcd and Lcm（常规积性函数求和，可分段打表）
• 51Nod 1847 - 奇怪的数学题（非常规积性函数求和，综合题，可分段打表）

【51nod 1244】莫比乌斯函数之和

$$\mathbb{M}(n)=1-\sum_{i=2}^n\mathbb{M}(\lfloor\frac{n}{i}\rfloor)$$

#include <cstdio>
#include <map>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
const int N=5000000;
int v[N+5],pri[500000],tot;
int mu[N+5];
map<LL,LL> s;
LL Query(LL n) {
    if (n<=N) return mu[n];
    if (s.count(n)) return s[n];
    LL ans=1;
    for (LL l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans-=(r-l+1)*Query(n/l);
    }
    return s[n]=ans;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
    #endif
    v[1]=mu[1]=1;
    F(i,2,N) {
        if (!v[i]) pri[++tot]=i,mu[i]=-1;
        F(j,1,tot) {
            if (i*pri[j]>N) break;
            v[i*pri[j]]=1;
            if (i%pri[j]!=0) mu[i*pri[j]]=-mu[i]; else break;
        }
    }
    F(i,1,N) mu[i]+=mu[i-1];
    LL a,b; scanf("%lld%lld",&a,&b);
    LL ansL=Query(a-1);
    printf("%lld\n",Query(b)-ansL);
    return 0;
}

【51nod 1239】欧拉函数求和

$$\sum_{d|n}\phi(d)=n$$
$$\sum_{i=1}^n\sum_{d|i}\phi(d)=\frac{n(n+1)}{2}$$
$$\sum_{i=1}^n\mathbb{M}(\lfloor\frac{n}{i}\rfloor)=\frac{n(n+1)}{2}$$
$$\mathbb{M}(n)=\frac{n(n+1)}{2}-\sum_{i=2}^n\mathbb{M}(\lfloor\frac{n}{i}\rfloor)$$

实现：

• 当数组大小比较大的时候，或者出现次数很多的时候，才设参数。
• 取模的正确姿势：
  ① 对于 int 类型的 a,b ，有：
  plus(a,b): (a+b)%L
multiply(a,b): 1LL*a*b%L
  ② 首项变成 long long
((LL)a-b+c-1LL*d*e%L)%L
  ③ 如果涉及到 long long 类型的乘法，先将 long long 转化为 int ，中间加空格。

inline int binom2(LL n) {
    return (n%2==0) ? ((n/2)%L) * ((n+1)%L) %L : ((n+1)/2)%L * (n%L) %L;
}

  总之如果 A 和 B 是两个运算的整体，那么写成 (A) * (B) % L 。

#include <cstdio>
#include <map>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
const int N=5000000;
const int L=(int)1e9+7;
int v[N+5],pri[500000],tot;
int phi[N+5];
map<LL,int> s;
int Query(LL n) {
    if (n<=N) return phi[n];
    if (s.count(n)) return s[n];
    int ans=( n%2==0 ? (n/2)%L * ((n+1)%L) %L : ((n+1)/2%L) * (n%L) %L );
    for (LL l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans=(ans- ((r-l+1)%L) * Query(n/l) %L )%L;
    }
    return s[n]=(ans+L)%L;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
    #endif
    v[1]=phi[1]=1;
    F(i,2,N) {
        if (!v[i]) pri[++tot]=i,phi[i]=i-1;
        F(j,1,tot) {
            if (i*pri[j]>N) break;
            v[i*pri[j]]=1;
            if (i%pri[j]!=0) phi[i*pri[j]]=phi[i]*phi[pri[j]];
            else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
        }
    }
    F(i,1,N) phi[i]=(phi[i]+phi[i-1])%L;
    LL n; scanf("%lld",&n);
    printf("%d\n",Query(n));
    return 0;
}