题目链接：
1239：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239
1244：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1244
杜教筛裸题，不过现在我也只会筛这俩前缀和...
$$s(n)=sum _{i=1}^{n}f(i)$$
那么就有：
$$sum_{i=1}^{n}f(i)lfloor frac{n}{i} floor=sum_{i=1}^{n}s(lfloor frac{n}{i} floor)=s(n)+sum_{i=2}^{n}s(lfloor frac{n}{i} floor)$$
移项得到：
$$s(n)=sum_{i=1}^{n}f(i)lfloor frac{n}{i} floor-sum_{i=2}^{n}s(lfloor frac{n}{i} floor)$$
对于欧拉函数，$f(n)=phi(n)$
$$sum_{i=1}^{n}phi(i)lfloor frac{n}{i} floor=sum_{i=1}^{n}sum_{d|n}phi(d)=sum_{i=1}^{n}i=frac{n*(n+1)}{2}$$
对于莫比乌斯函数，$f(n)=mu(n)$
$$sum_{i=1}^{n}mu(i)lfloor frac{n}{i} floor=sum_{i=1}^{n}sum_{d|n}mu(d)=sum_{i=1}^{n}[i=1]=1$$
然后这两个公式就可以在线筛预处理$n^{frac{2}{3}}$只后记忆化达到$O(n^{frac{2}{3}})$的效率.
值得注意的就是，记忆化要写hash，以及不要忘了取模，筛欧拉函数前缀和时牵扯取模和除2，可以先讨论奇偶除掉2再计算。
1239：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 5000000
#define P 233333
#define MAXN 250000
#define MO 1000000007
int cnt,prime[N+10],flag[N+10];
LL X,phi[N+10];
inline void Pre(LL n)
{
flag[1]=1; phi[1]=1;
for (LL i=2; i<=n; i++)
{
if (!flag[i]) prime[++cnt]=i,phi[i]=i-1;
for (int j=1; j<=cnt && i*prime[j]<=n; j++)
{
flag[i*prime[j]]=1;
if (!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j]; break;}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
for (LL i=1; i<=n; i++) phi[i]=(phi[i]+phi[i-1])%MO;
}
struct Hash{
int next; LL i,x;
}mp[MAXN];
int head[MAXN],tot;
inline void Add(LL i,LL x) {int pos=i%P; tot++; mp[tot].next=head[pos]; head[pos]=tot; mp[tot].i=i; mp[tot].x=x;}
inline LL Sum(LL x)
{
if (x<=N) return phi[x];
else
{
int pos=x%P;
for (int i=head[pos]; i; i=mp[i].next)
if (mp[i].i==x) {return mp[i].x;}
}
LL sum=0,s=0;
for (LL i=2,j; i<=x; i=j+1)
j=x/(x/i),(sum+=Sum(x/i)%MO*(j-i+1)%MO)%=MO;
if (x&1) s=(((x+1)/2)%MO)*(x%MO)%MO; else s=((x/2)%MO)*((x+1)%MO)%MO;
sum=(s-sum+MO)%MO;
Add(x,sum);
return sum;
}
int main()
{
scanf("%lld",&X);
Pre(N);
printf("%lld
",Sum(X));
return 0;
}
1244
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
#define P 233333
#define N 5000000
#define MAXN 250000
int cnt,prime[N+10],flag[N+10];
LL L,R,mu[N+10];
inline void Pre(LL n)
{
flag[1]=1; mu[1]=1;
for (LL i=2; i<=n; i++)
{
if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
for (int j=1; j<=cnt && i*prime[j]<=n; j++)
{
flag[i*prime[j]]=1;
if (!(i%prime[j])) {mu[i*prime[j]]=0; break;}
mu[i*prime[j]]=-mu[i];
}
}
for (LL i=1; i<=n; i++) mu[i]+=mu[i-1];
}
struct Hash{
int next; LL i,x;
}mp[MAXN];
int head[MAXN],tot;
inline void Add(LL i,LL x) {int pos=i%P; tot++; mp[tot].next=head[pos]; head[pos]=tot; mp[tot].i=i; mp[tot].x=x;}
inline LL Sum(LL x)
{
if (x<=N) return mu[x];
else
{
int pos=x%P;
for (int i=head[pos]; i; i=mp[i].next)
if (mp[i].i==x) {return mp[i].x;}
}
LL sum=0;
for (LL i=2,j; i<=x; i=j+1)
j=x/(x/i),sum+=Sum(x/i)*(j-i+1);
Add(x,1LL-sum);
return 1LL-sum;
}
int main()
{
scanf("%lld%lld",&L,&R);
Pre(N);
printf("%lld
",Sum(R)-Sum(L-1));
return 0;
}