链接:https://ac.nowcoder.com/acm/contest/61132/A 来源:牛客网 总所周知集训队里有个人很喜欢学数学=.=,今天他突然觉得给新生放一道NTT有点太难了,于是他紧急想了一道很简单的数学题,题面也很短,给定一个k,求 ( ∑ � = 1 � ∑ � = 1 � � ( � ) ∗ ⌊ � / � ⌋ ) (∑ n=1 k ∑ i=1 n φ(i)∗⌊n/i⌋)%mod,其中 � ( � ) φ(i)表示i的欧拉函数, ⌊ � / � ⌋ ⌊n/i⌋表示n除以i向下取整,mod=1000000007,很简单吧,秒了它。
时间: 2024-04-13 11:25:34 浏览: 46
这道题目是求一个表达式的结果,表达式中包含了欧拉函数和向下取整操作。需要注意的是,最后结果需要对一个给定的mod取模。
首先,我们可以把这个表达式分成两部分来计算。第一部分是计算φ(i)的前缀和,第二部分是计算⌊n/i⌋的前缀和。
对于第一部分,我们可以使用线性筛法来计算φ(i)的前缀和。具体步骤如下:
1. 初始化一个数组phi,大小为k+1,用来保存欧拉函数的值。
2. 初始化一个数组prime,用来保存质数。
3. 初始化一个数组isPrime,大小为k+1,用来标记是否是质数。
4. 初始化一个数组sumPhi,大小为k+1,用来保存φ(i)的前缀和。
5. 遍历2到k的每个数i,如果isPrime[i]为true,则将i加入到prime数组中,并且令phi[i] = i-1。
否则,找到i的最小质因数p,令phi[i] = phi[i/p] * p / (p-1)。
6. 遍历prime数组中的每个质数p,更新phi数组中所有p的倍数的值,令phi[i] = phi[i] * p / (p-1)。
7. 计算sumPhi数组的前缀和,即sumPhi[i] = sumPhi[i-1] + phi[i]。
对于第二部分,我们可以使用容斥原理来计算⌊n/i⌋的前缀和。具体步骤如下:
1. 初始化一个数组sumDiv,大小为k+1,用来保存⌊n/i⌋的前缀和。
2. 遍历1到k的每个数i,计算sumDiv[i] = sumDiv[i-1] + ⌊n/i⌋。
3. 使用容斥原理,减去所有的sumDiv[i] * φ(i),其中i为k的因子。
最后,将第一部分和第二部分的结果相乘,并对mod取模,即可得到最终结果。
以上就是求解这道题目的思路和步骤。希望对你有帮助!如果有任何疑问,请随时提问。