4176: Lucas的数论

4176: Lucas的数论

Time Limit: 30 Sec   Memory Limit: 256 MB Submit: 247   Solved: 172 [ Submit][ Status][ Discuss]

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。

Source

[ Submit][ Status][ Discuss]  #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int M = 9999987; const int Mod = 999987; typedef long long LL; const LL mo = 1000000007; struct data{ int Num,val; data(){} data(int Num,int val): Num(Num),val(val){} }; int tot,Ans,mu[M],pri[M]; bool not_pri[M]; vector <data> v[Mod]; int Mul(const LL &x,const LL &y) {return x * y % mo;} int Add(const int &x,const int &y) {return x + y < mo ? x + y : x + y - mo;} int Dec(const int &x,const int &y) {return x - y >= 0 ? x - y : x - y + mo;} void Pre_Work() { mu[1] = 1; for (int i = 2; i < M; i++) { if (!not_pri[i]) pri[++tot] = i,mu[i] = mo - 1; for (int j = 1; j <= tot; j++) { int Nex = i * pri[j]; if (Nex >= M) break; not_pri[Nex] = 1; if (i % pri[j] == 0) {mu[Nex] = 0; break;} mu[Nex] = Mul(mu[i],mu[pri[j]]); } } for (int i = 2; i < M; i++) mu[i] = Add(mu[i],mu[i - 1]); } int Search(int N) { int pos = N % Mod; for (int i = 0; i < v[pos].size(); i++) if (v[pos][i].Num == N) return v[pos][i].val; return -1; } void Insert(int Num,int val) { int pos = Num % Mod; v[pos].push_back(data(Num,val)); } int Calc_f(int N) { if (N < M) return mu[N]; int ret = Search(N); if (ret != -1) return ret; ret = 1; for (int i = 2,last; i <= N; i = last + 1) { last = N / (N / i); int A = Calc_f(N / i); int B = (last - i + 1); ret = Dec(ret,Mul(A,B)); } Insert(N,ret); return ret; } int Calc_g(int N) { int ret = 0; for (int i = 1,last; i <= N; i = last + 1) { last = N / (N / i); ret = Add(ret,Mul(last - i + 1,N / i)); } return Mul(ret,ret); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif Pre_Work(); int n; cin >> n; for (int i = 1,last; i <= n; i = last + 1) { last = n / (n / i); int A = Dec(Calc_f(last),Calc_f(i - 1)); int B = Calc_g(n / i); Ans = Add(Ans,Mul(A,B)); } cout << Ans << endl; return 0; }