首页 > 代码库 > BZOJ4176 Lucas的数论
BZOJ4176 Lucas的数论
4176: Lucas的数论
Time Limit: 30 Sec Memory Limit: 256 MBDescription
去年的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。
好吧，下午有点颓废。。。
首先用到BZOJ3944的结论
然后直接上杜教筛。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 template <class _T> inline void read(_T &_x) { 4 int _t; bool flag = false; 5 while ((_t = getchar()) != ‘-‘ && (_t < ‘0‘ || _t > ‘9‘)) ; 6 if (_t == ‘-‘) _t = getchar(), flag = true; _x = _t - ‘0‘; 7 while ((_t = getchar()) >= ‘0‘ && _t <= ‘9‘) _x = _x * 10 + _t - ‘0‘; 8 if (flag) _x = -_x; 9 }10 typedef long long LL;11 const int maxn = 2e6;12 const int mod = 1000000007;13 int mu[maxn], prime[maxn], pcnt;14 bool vis[maxn];15 inline int mul(int a, int b) {return (int)((LL)a * b % mod); }16 inline void add(int &a, int b) {a += b; if (a < 0) a += mod; if (a >= mod) a -= mod; }17 inline void init() {18 mu[0] = 0, mu[1] = 1;19 for (register int i = 2; i < maxn; ++i) {20 if (!vis[i]) {21 prime[++pcnt] = i;22 mu[i] = -1;23 }24 for (register int j = 1, tmp; j <= pcnt && (tmp = prime[j] * i) < maxn; ++j) {25 vis[tmp] = true;26 if (i % prime[j] == 0) {27 mu[tmp] = 0;28 break;29 }30 mu[tmp] = -mu[i];31 }32 }33 for (register int i = 2; i < maxn; ++i) mu[i] += mu[i - 1];34 }35 map<int, int> Mmu;36 int Mu(int n) {37 if (n < maxn) return mu[n];38 if (Mmu.find(n) != Mmu.end()) return Mmu[n];39 int ret = 1;40 for (int i = 2, j, t; i <= n; i = j + 1) {41 t = n / i, j = n / t;42 add(ret, -mul(Mu(t), j - i + 1));43 }44 Mmu[n] = ret;45 return ret;46 }47 inline int F_2(int n) {48 int ret = 0;49 for (register int i = 1, j, t; i <= n; i = j + 1) {50 t = n / i, j = n / t;51 add(ret, mul(t, (j - i + 1)));52 }53 return mul(ret, ret);54 }55 inline int calc(int n) {56 int ret = 0;57 for (int i = 1, j, t; i <= n; i = j + 1) {58 t = n / i, j = n / t;59 add(ret, mul(Mu(j) - Mu(i - 1), F_2(t)));60 }61 return ret;62 }63 int main() {64 //freopen(".in", "r", stdin);65 //freopen(".out", "w", stdout);66 init();67 int n; read(n);68 cout << calc(n) << endl;69 return 0;70 }
BZOJ4176 Lucas的数论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。