首页 > 代码库 > 【BZOJ4176】 Lucas的数论
【BZOJ4176】 Lucas的数论
Description
去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。
在整理以前的试题时，发现了这样一道题目“求Sigma(f(i)),其中1<=i<=N”，其中 表示i的约数个数。他现在长大了，题目也变难了。
求如下表达式的值：
其中 表示ij的约数个数。
他发现答案有点大，只需要输出模1000000007的值。
Input
第一行一个整数n。
Output
一行一个整数ans，表示答案模1000000007的值。
Sample Input
2
Sample Output
8
HINT
对于100%的数据n <= 10^9。
Solution
因为直接用编辑器打公式比较麻烦且丑，就用markdown截图完传图片了= =b。
Code
1 #include <cstdio> 2 #include <cmath> 3 4 #define R register 5 const int mod = 1e9 + 7; 6 #define maxn 1500010 7 int miu[maxn], smiu[maxn], pr[maxn / 10], prcnt, lim, N; 8 bool vis[maxn]; 9 int hash[maxn];10 bool vihash[50000];11 int Miu(R int n)12 {13 if (n <= lim) return smiu[n];14 if (vihash[N / n]) return hash[N / n];15 16 vihash[N / n] = 1;17 R int ret = 1;18 for (R int i = 2, j; i <= n; i = j + 1)19 {20 j = n / (n / i);21 (ret += mod - 1ll * (j - i + 1) * Miu(n / i) % mod) %= mod;22 }23 return hash[N / n] = ret;24 }25 inline int sumf(R int n)26 {27 R int ret = 0;28 for (R int i = 1, j; i <= n; i = j + 1)29 {30 j = n / (n / i);31 ret = (ret + 1ll * (j - i + 1) * (n / i)) % mod;32 }33 return ret;34 }35 int main()36 {37 scanf("%d", &N);38 lim = (int) pow(N * 1.0, 0.666);39 // printf("%d\n", lim);40 miu[1] = smiu[1] = 1;41 for (R int i = 2; i <= lim; ++i)42 {43 if (!vis[i]) pr[++prcnt] = i, miu[i] = -1;44 smiu[i] = (smiu[i - 1] + miu[i]) % mod;45 for (R int j = 1; j <= prcnt && 1ll * i * pr[j] <= lim; ++j)46 {47 vis[i * pr[j]] = 1;48 if (i % pr[j]) miu[i * pr[j]] = -miu[i];49 else50 {51 miu[i * pr[j]] = 0;52 break;53 }54 }55 }56 R int ans = 0, last = 0;57 for (R int i = 1, j; i <= N; i = j + 1)58 {59 j = N / (N / i);60 R int Ph = Miu(j);61 R int fs = sumf(N / i);62 // printf("l = %d r = %d %d %d\n", i, j, Ph, fs);63 ans = (ans + 1ll * (Ph - last + mod) * fs % mod * fs) % mod;64 last = Ph;65 }66 // printf("%d\n", last);67 printf("%d\n", ans % mod);68 return 0;69 }
【BZOJ4176】 Lucas的数论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。