题目描述
Two positive integers $a$ and $b$ are 2-friendly when $gcd(a,b)=2^t,t>0$. For example, $24$ and $40$ are 2-friendly because $gcd(24,40)=8=2^3$ while $24$ and $36$ are not because $gcd(24,36)=12=2^2\cdot 3$ not a power of $2$.
Let $f(n)$ be the number of pairs, $(p,q)$, of positive integers with $1\leq p<q\leq n$ such that $p$ and $q$ are 2-friendly. You are given $f(10^2)=1031$ and $f(10^6)=321418433$ modulo $1000000007$ .
Find $f(10^{11})$ modulo $1000000007$.
题意
问你所有满足$1\leq p<q\leq 1e11$,并且$gcd(p,q)==2^t$的对数
分析
显然可以对于每个$2^t$单独考虑,不妨设$2^t = x$,可以得到
$$
ans = \sum_{x = 2的幂}^{upper}\sum_{i=1}^{upper/x} \varphi(i)
$$
显然有 : $\varphi(i) \star I = id$ 。我们记 $S(n) = \sum_{i=1}^{n} \varphi(i)$ 。
对于上述卷积式,两边求和有:
$$
\sum_{i=1}^{n} id(i) = \sum_{i=1}^{n} \sum_{d|i} I(d) \cdot \varphi(\frac{i}{d})
$$
$$
\sum_{i=1}^{n} id(i) = \sum_{d=1}^{n} I(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \varphi(i)
$$
$$
\sum_{i=1}^{n}id(i) = \sum_{d = 1}^{n}I(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
$$
$$
\sum_{i=1}^{n} id(i) = I(1)\cdot S(n) + \sum_{d=2}^{n}I(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
$$
$$
\frac{n\cdot(n+1)}{2} = S(n) + \sum_{d=2}^{n}I(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
$$
$$
S(n) = \frac{n\cdot(n+1)}{2} - \sum_{d=2}^{n}I(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
$$
然后分块一下,递归搞下去就行了$\dots$
代码
给大佬递上我奇丑无比的代码 (/ω\)
1 |
|