\(\mathcal{Description}\)

Link.

积性函数 \(f\) 满足 \(f(p^c)=p\oplus c~(p\in\mathbb P,c\in\mathbb N_+)\)，求 \(\sum_{i=1}^n f(i)\bmod(10^9+7)\)。

\(\mathcal{Solution}\)

首先，考虑 \(f\) 的素数点值：

\[f(p)=\begin{cases}
3,&p=2\\
p-1,&\text{otherwise}
\end{cases}
\]

由 \(p-1\) 联想到 \(\varphi(p)=p-1\)，可惜 \(\varphi(2)=1\)。干脆一点，我们直接强行把 \(\varphi\) 的偶数点值乘上 \(3\)，令

\[g(n)=\begin{cases}
\varphi(n),&2\not\mid n\\
3\varphi(n),&\text{otherwise}
\end{cases}
\]

显然它也是积性函数。

接着，求 \(g\) 的前缀和。其前缀和为 \(\varphi\) 的前缀和加上两倍偶数点的 \(\varphi\) 前缀和。记

\[\begin{aligned}
S(n)&=\sum_{i=1}^n\varphi(2i)\\
&=\sum_{i=1}^n[2\not\mid i]\varphi(i)+2\sum_{i=1}^n[2\mid i]\varphi(i)\\
&=S\left(\frac{n}{2}\right)+\sum_{i=1}^n\varphi(i)
\end{aligned}
\]

杜教筛处理 \(\varphi\) 的前缀，\(S\) 就能在可观（我不会算 qwq）的复杂度内预处理出来，继而也得到了 \(g\) 的 \(\mathcal O(\sqrt n)\) 个前缀和。

此外，我们还需要求 \(h(i)\)，即求 \(h(p^c)~(c>1)\)。考虑 \(f(p^c)\) 与它的关系：

\[f(p^c)=\sum_{i=0}^ch(p^i)g(p^{c-i})\\
\Rightarrow~~~~h(p^c)=f(p^c)-\sum_{i=0}^{c-1}h(p^i)g(p^{c-i})
\]

顺手把 \(\mathcal O(\sqrt n\ln\ln\sqrt n)\)（\(n\) 以内素数的倒数和的规模是 \(\mathcal O(\ln\ln n)\)）个 \(h(p^c)\) 也预处理出来，最后 \(\mathcal O(\sqrt n)\) 搜索 Powerful Number 就能求出答案啦！

\(\mathcal{Code}\)

/* Clearink */

#include <cmath>

#include <cstdio>

#include <vector>

#include <unordered_map>

#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )

#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )

typedef long long LL;

const int MAXS = 1e7, MAXSN = 1e5, MOD = 1e9 + 7, INV2 = 500000004;

int pn, pr[MAXS + 5], phi[MAXS + 5], phis[MAXS + 5];

bool npr[MAXS + 5];

std::vector<int> gpr[MAXSN + 5];

inline int mul( const long long a, const int b ) { return a * b % MOD; }

inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }

inline void subeq( int& a, const int b ) { ( a -= b ) < 0 && ( a += MOD ); }

inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }

inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }

inline void sieve() {

	phi[1] = phis[1] = 1;

	rep ( i, 2, MAXS ) {

		if ( !npr[i] ) phi[pr[++pn] = i] = i - 1;

		for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= MAXS; ++j ) {

			npr[t] = true;

			if ( !( i % pr[j] ) ) { phi[t] = phi[i] * pr[j]; break; }

			phi[t] = phi[i] * ( pr[j] - 1 );

		}

		phis[i] = add( phis[i - 1], phi[i] );

	}

}

inline int phiSum( const LL n ) {

	static std::unordered_map<LL, int> mem;

	if ( n <= MAXS ) return phis[n];

	if ( mem.count( n ) ) return mem[n];

	int ret = mul( mul( n % MOD, ( n + 1 ) % MOD ), INV2 );

	for ( LL l = 2, r; l <= n; l = r + 1 ) {

		r = n / ( n / l );

		subeq( ret, mul( ( r - l + 1 ) % MOD, phiSum( n / l ) ) );

	}

	return mem[n] = ret;

}

inline int ephiSum( const LL n ) {

	if ( !n ) return 0;

	return add( ephiSum( n >> 1 ), phiSum( n ) );

}

LL n;

int sn, sum[MAXSN * 2 + 5];

inline void initInvG() {

	rep ( i, 1, pn ) {

		if ( 1ll * pr[i] * pr[i] > n ) break;

		std::vector<int>& curg( gpr[i] );

		curg.push_back( 1 ), curg.push_back( 0 );

		LL pwr = 1ll * pr[i] * pr[i];

		for ( int j = 2; pwr <= n; ++j, pwr *= pr[i] ) {

			int g = pr[i] ^ j;

			LL pwc = pr[i];

			for ( int k = j - 1; ~k; --k, pwc *= pr[i] ) {

				subeq( g,

					mul( ( pwc / pr[i] * ( pr[i] ^ 1 ) ) % MOD, curg[k] ) );

			}

			curg.push_back( g );

		}

	}

}

inline int powerSum( const int pid, LL x, const int g ) {

	if ( !g ) return 0;

	int ret = 0, p = pr[pid];

	if ( pid == 1 || !( x % pr[pid - 1] ) ) {

		addeq( ret, mul( g, x > sn ? sum[n / x] : sum[sn + x] ) );

	}

	if ( ( x *= p ) > n ) return ret;

	if ( ( x *= p ) > n ) return ret;

	addeq( ret, powerSum( pid + 1, x / ( 1ll * p * p ), g ) );

	for ( int i = 2; x <= n; ++i, x *= p ) {

		addeq( ret, powerSum( pid + 1, x, mul( g, gpr[pid][i] ) ) );

	}

	return ret;

}

int main() {

	sieve();

	scanf( "%lld", &n ), sn = sqrt( 1. * n );

	rep ( i, 1, sn ) sum[i] = add( phiSum( i ), mul( 2, ephiSum( i >> 1 ) ) );

	rep ( i, 1, sn ) {

		sum[i + sn] = add( phiSum( n / i ), mul( 2, ephiSum( n / i >> 1 ) ) );

	}

	initInvG();

	printf( "%d\n", powerSum( 1, 1, 1 ) );

	return 0;

}

巴特西

Solution -「LOJ #6053」简单的函数

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章