这个是一个处理积极性函数前缀和的东西, 先把能处理的范围的函数值处理出来, 然后数论分块, 递归处理这些值, 一点点缩小这个的范围, 从而计算出函数值.
具体看代码就行了, 不是很难.
洛谷的模板题是处理μ和φ的前缀和.
代码:
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<ctime>
- #include<queue>
- #include<algorithm>
- #include<cstring>
- #include<unordered_map>
- using namespace std;
- #define duke(i,a,n) for(register int i = a;i <= n;i++)
- #define lv(i,a,n) for(register int i = a;i>= n;i--)
- #define clean(a) memset(a,0,sizeof(a))
- const int INF = 1 <<30;
- typedef long long ll;
- typedef double db;
- template <class T>
- void read(T &x)
- {
- char c;
- bool op = 0;
- while(c = getchar(), c <'0' || c> '9')
- if(c == '-') op = 1;
- x = c - '0';
- while(c = getchar(), c>= '0' && c <= '9')
- x = x * 10 + c - '0';
- if(op) x = -x;
- }
- template <class T>
- void write(T x)
- {
- if(x <0) putchar('-'), x = -x;
- if(x>= 10) write(x / 10);
- putchar('0' + x % 10);
- }
- const int N = 5e6 + 5;
- int miu[N + 2],flag[N + 2],pri[N + 5];
- ll phi[N + 2],tot = 0;
- unordered_map <int,ll> ansmiu,ansphi;
- void init()
- {
- miu[1] = 1;
- phi[1] = 1;
- duke(i,2,N)
- {
- if(!flag[i])
- {
- pri[++tot] = i;
- phi[i] = i - 1;
- miu[i] = -1;
- }
- for(int j = 1;j <= tot;j++)
- {
- if(i * pri[j]> N) break;
- flag[i * pri[j]] = 1;
- if(i % pri[j] == 0)
- {
- phi[i * pri[j]] = phi[i] * pri[j];
- break;
- }
- miu[i * pri[j]] = -miu[i];
- phi[i * pri[j]] = phi[i] * (pri[j] - 1);
- }
- }
- duke(i,2,N)
- {
- miu[i] += miu[i - 1];
- phi[i] += phi[i - 1];
- }
- }
- int t;
- ll phis(int n)
- {
- if(n <= N)
- {
- return phi[n];
- }
- if(ansphi.count(n)) return ansphi[n];
- ll ans = (1LL * n * (n + 1))>> 1;
- for(int l = 2,r;l <= n;l = r + 1)
- {
- r = n / (n / l);
- ans -= (r - l + 1) * phis(n / l);
- }
- ansphi[n] = ans;
- return ans;
- }
- ll mius(int n)
- {
- if(n <= N)
- {
- return miu[n];
- }
- if(ansmiu.count(n)) return ansmiu[n];
- ll ans = 1;
- for(int l = 2,r;l <= n;l = r + 1)
- {
- r = n / (n / l);
- ans -= (r - l + 1) * mius(n / l);
- }
- ansmiu[n] = ans;
- return ans;
- }
- int main()
- {
- init();
- read(t);
- while(t--)
- {
- int n;
- read(n);
- printf("%lld %lld\n",phis(n),mius(n));
- }
- return 0;
- }
[模板] 杜教筛
来源: http://www.bubuko.com/infodetail-2922308.html