[51Nod 1244] - 莫比乌斯函数之和
求
开推
移项
此处是杜教筛的精髓,也是整除分块优化的精髓(或者说是转换方法),枚举i是d的多少倍
令,则有
那么就可以用线性筛出前面一部分,再整除分块优化递归处理
杜教筛无预处理的时间复杂度是
预处理一定范围内的答案后就能降到
然而我们此处并不需要多小的时间复杂度…随便处理一个就能过了
AC code
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXP = 1e7+1;
int Prime[MAXP/10], Cnt, mu[MAXP], sum[MAXP];
bool IsnotPrime[MAXP];
map<LL,int>S;
void init(int N)
{
mu[1] = 1;
for(int i = 2; i <= N; ++i)
{
if(!IsnotPrime[i]) Prime[++Cnt] = i, mu[i] = -1;
for(int j = 1; j <= Cnt && i * Prime[j] <= N; ++j)
{
IsnotPrime[i * Prime[j]] = 1;
if(i % Prime[j] == 0) { mu[i * Prime[j]] = 0; break; }
mu[i * Prime[j]] = -mu[i];
}
}
for(int i = 1; i <= N; i++) sum[i] = sum[i-1] + mu[i];
}
inline int solve(LL N)
{
if(N < MAXP) return sum[N];
if(S.count(N)) return S[N];//记忆化,其实此处可以Hash或者用
int ret = 1;
for(LL i = 2, j; i <= N; i=j+1)
{
j = N/(N/i);
ret -= (j-i+1) * solve(N/i);
}
return S[N] = ret;
}
int main ()
{
LL n, m; init(MAXP-1);
scanf("%lld%lld", &n, &m);
printf("%d
", solve(m)-solve(n-1));
}
[51Nod 1239] - 欧拉函数之和
求
开推,有
移项
令,则有
然后…就没有了.像上一道题一样处理就完了
AC Code
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXP = 5e6 + 1;
const int mod = 1e9 + 7;
const int inv2 = 500000004;
int Prime[MAXP/10], Cnt, phi[MAXP];
LL sum_phi[MAXP];
bool IsnotPrime[MAXP];
void init(int N)
{
phi[1] = 1;
for(LL i = 2; i <= N; ++i)
{
if(!IsnotPrime[i]) Prime[++Cnt] = i, phi[i] = i-1;
for(LL j = 1; j <= Cnt && i * Prime[j] <= N; ++j)
{
IsnotPrime[i * Prime[j]] = 1;
if(i % Prime[j] == 0)
{
phi[i * Prime[j]] = phi[i] * Prime[j];
break;
}
phi[i * Prime[j]] = phi[i] * (Prime[j]-1);
}
}
for(int i = 1; i <= N; i++)
sum_phi[i] = ((sum_phi[i-1] + phi[i]) % mod + mod) % mod;
}
map<LL, LL> S_phi;
inline LL solve_phi(LL N)
{
if(N < MAXP) return sum_phi[N];
if(S_phi.count(N)) return S_phi[N];
LL ret = (N%mod + 1) * (N%mod) % mod * inv2 % mod;
for(LL i = 2, j; i <= N; i=j+1)
{
j = N/(N/i);
ret = (ret - (j-i+1) % mod * solve_phi(N/i) % mod) % mod;
}
return S_phi[N] = ((ret + mod) % mod);
}
int main ()
{
init(MAXP-1); LL n;
scanf("%lld", &n);
printf("%lld
", solve_phi(n));
}