题目描述
求题目分析
乍一看十分像裸莫比乌斯反演,然而的范围让人望而却步
于是先变化一下式子
枚举
令k=Td
则此时可以整除分块优化,每次算出相等的上下界
后用莫比乌斯反演计算
由于计算的前缀和时记忆化处理过,所以在杜教筛外面再套了一个整除分块优化不会影响时间复杂度,复杂度仍是
AC Code
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int MAXN = 5e6+1;
const int inv2 = 500000004;
map<LL, LL> S; LL s[MAXN];
int Prime[MAXN], Cnt, phi[MAXN];
bool IsnotPrime[MAXN];
void init()
{
phi[1] = 1;
for(int i = 2; i < MAXN; ++i)
{
if(!IsnotPrime[i]) Prime[++Cnt] = i, phi[i] = i-1;
for(int j = 1; j <= Cnt && i * Prime[j] < MAXN; ++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] * phi[Prime[j]];
}
}
for(int i = 1; i < MAXN; ++i) s[i] = (s[i-1] + phi[i]) % mod;
}
inline LL sum(LL n)
{
if(n < MAXN) return s[n];
if(S.count(n)) return S[n];
LL ret = (n%mod) * ((n+1)%mod) % mod * inv2 % mod;
for(LL i = 2, j; i <= n; i=j+1)
{
j = n/(n/i);
ret = (ret - sum(n/i) * ((j-i+1)%mod) % mod) % mod;
}
return S[n] = ret;
}
inline LL solve(LL n)
{
LL ret = 0;
for(LL i = 1, j; i <= n; i=j+1)
{
j = n/(n/i);
ret = (ret + ((n/i)%mod) * ((n/i)%mod) % mod * ((sum(j)-sum(i-1))%mod) % mod) % mod;
}
return ret;
}
int main ()
{
init(); LL n;
scanf("%lld", &n);
printf("%lld\n", (solve(n)+mod)%mod);
}