Min_25

题目背景

模板题，无背景。

题目描述

定义积性函数f(x)，且(f(p^k)= p^k (p^k − 1))（p是一个质数），求

[huge displaystyle sum_{i=1}^{n}f(x) ]

对109+7取模。

输入格式

一行一个整数n。

输出格式

一个整数表示答案。

输入输出样例

输入 #1

输出 #1

输入 #2

1000000000

输出 #2

710164413

说明/提示

(n <= 1e10)

Min_25筛是个神奇的东西，在这写一下我的理解，其实背过就好了。。。。

首先 Min_25筛的适用范围是(f(p) 和 f(p^k)) 在p是质数是比较好求，且n很大。

Pre

将 n 整除分块作为，以后的 dp 用到的值。

step 1

计算质数的贡献

类似dp ，设(g(n , j)) 表示在前n个数中，最小质因子 >= (P_j) 的数，或者是质数的 f 的和。

[g(n , j) = g(n , j - 1) (p_j^2 > n) \ g(n , j) = g(n , j - 1) - f(p_j) * (g(leftlfloorfrac{n}{p_j} ight floor , j - 1) - sum_{i=1}^{j-1}f(P_j)) P_j^2 <= n ]

(g(n , 0)) 也就是所有，数的 f 值

step 2

计算合数的贡献

设 (s(n , j)) 表示最小质因子 >= (P_j) 的 f 值之和。

那他有两部分构成一部分是质数，另一部分是合数。

质数的可以是 (huge g(n , |P|) - displaystyle sum_{i=1}^{j-1}f(P_i))

合数的就暴力枚举，最小质因子以及他的次数

[S(n , j) = g(n , |P|) - sum_{i=1}^{j-1}f(P_i) + sum_{k=j}^{P_k^2 <=n}sum_{e=1}^{P_K^{e+1}<=n}S(leftlfloorfrac{n}{P_k^e} ight floor , k + 1) * f(P_k^e) + f(P_k^{e+1}) ]

巨佬的讲解

其实吧就是为了存个代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long 
const int N = 1e6+100;
const int mod = 1e9+7;
const long long inv6 = 166666668;
const long long inv2 = 500000004;
#define RQ puts("RQ");
long long n;
int m , Sqr , tot;
int vis[N] , id1[N] , id2[N];
long long sp[N] , sp2[N] , g[N] , h[N] , w[N] , prime[N];
inline int id(long long val) { return val <= Sqr ? id1[val] : id2[n / val]; }

void Init(int maxn)
{
	for(int i = 2 ; i <= maxn ; ++i) // sp[tot]!!!
	{
		if(vis[i] == 0) prime[++tot] = i , sp[tot] = (sp[tot-1] + i) % mod , sp2[tot] = (sp2[tot-1] + 1LL * i * i % mod) % mod;
		for(int j = 1 ; j <= tot && prime[j] * i <= maxn ; ++j)
		{
			vis[i * prime[j]] = 1;
			if(i * prime[j] == 0) break;
		}
	}
	return ;
}

long long ksm(int a , int k)
{
	long long ans = 1;
	for( ; k ; k >>= 1 , a = 1LL * a * a % mod)
		if(k & 1) ans = ans * a % mod;
	return ans;
}

long long solve(long long n , int p)
{
	if(n <= 1 || prime[p] > n) return 0;
	int k = id(n);
	long long res = (h[k] - sp2[p-1]) % mod - (g[k] - sp[p-1]) % mod;
	res = (res % mod + mod) % mod;
	for(int i = p ; i <= tot && 1LL * prime[i] * prime[i] <= n ; ++i)
	{
		long long p1 = prime[i] , p2 = 1LL * prime[i] * prime[i];
		for(int e = 1 ; p2 <= n ; e++ , p1 = p2 , p2 *= prime[i])
			res = (res + (solve(n / p1 , i + 1) * ((p1%mod) * (p1%mod - 1) % mod) % mod + ((p2%mod) * (p2%mod - 1) % mod)) % mod) % mod;
	}
	return (res%mod+mod)%mod;
}

signed main()
{
	cin >> n; Sqr = sqrt(n); Init(Sqr);
	for(long long i = 1 ; i <= n ; i = (n / w[m]) + 1)
	{
		w[++m] = n / i;
		if(w[m] <= Sqr) id1[w[m]] = m; else id2[n / w[m]] = m;
		g[m] = ((w[m] + 2) % mod * ((w[m] - 1) % mod)) % mod; 
		g[m] = g[m] * inv2 % mod;
		h[m] = ((w[m] % mod * ((w[m] + 1) % mod)) % mod * ((w[m] * 2 % mod + 1) % mod)) % mod; 
		h[m] = h[m] * inv6 % mod; h[m] = ((h[m] - 1) % mod + mod) % mod; // ----1111
	}
	for(int j = 1 ; j <= tot ; ++j)
		for(int i = 1 ; i <= m && 1LL * prime[j] * prime[j] <= w[i] ; ++i)
		{
			int k = id(w[i] / prime[j]);
			g[i] = (g[i] - 1LL * prime[j] * (g[k] - sp[j-1]) % mod) % mod; 
			g[i] = (g[i] % mod + mod) % mod;
			h[i] = (h[i] - 1LL * prime[j] * prime[j] % mod * (h[k] - sp2[j-1]) % mod) % mod; 
			h[i] = (h[i] % mod + mod) % mod;
		}
	long long ans = solve(n , 1) + 1;
	printf("%lld
" , ans % mod);
	return 0;
}
/*
9999998765 
38860607
*/