题目链接
欧拉函数$\phi(n)$被定义$1$~$n$中与$n$互质的数的个数。例如$\phi(5)=4$,因为$1$,$2$,$3$,$4$这四个数字与$5$互质。
定义$f$函数:$$f(n, k)=\sum\limits_{i=k}^{n-k}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
给定$n$和$k$,其中$2\le n\le 10^{12}$,$1\le k\le min(\lfloor\frac{n}{i}\rfloor,1000000)$,求$f(n,k)$的值。
简化公式
一看到这个就想到了求欧拉函数的前缀和然后杜教筛之类的。
但是当我着手做的时候发现这个$n$太大了,$O(n^{\frac{3}{4}})$的复杂度无法忍受。
于是我就想到这个$\lfloor\frac{n}{i}\rfloor$一定是有什么作用的,于是发现了一些不得了的事。
令
$$g(n)=\sum\limits_{i=1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
$$=\sum\limits_{i=1}^{n}\phi(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}1$$
$$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\phi(i)$$
重头戏来了,这个式子特别像使用杜教筛时中间的某个式子,于是我们可以把它逆过来用。
$$g(n)=\sum\limits_{i=1}^{n}\sum\limits_{d|i}\phi(d)$$
$$=\sum\limits_{i=1}^{n}i=\frac{n\cdot(n+1)}{2}$$
那么
$$f(n,k)=g(n)-\sum\limits_{i=1}^{k-1}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor-\sum\limits_{i=n-k+1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
$$=\frac{n\cdot(n+1)}{2}-\sum\limits_{i=1}^{k-1}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor-\sum\limits_{i=n-k+1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
然后我们就可以先用欧拉筛求出$\sqrt{n}$内的欧拉函数值以及所有的素数。然后用区间筛求出区间$[n-k+1,n]$之间的欧拉函数值。
复杂度$O(\sum\limits_{p\le \sqrt{n}}\lfloor\frac{k}{p}\rfloor+k+\sqrt{n})\approx O(能过)$
小技巧
在处理$(a×b×…)%m$时粗心的小伙伴总会因为太复杂而出错。
这样写基本上就不会出错了。
虽然可能会比较慢,但一般不会卡这个常吧。
1 2 3 4 5 6 7 8 9 10 11
| long long mod(long long x, long long p) { return ((x % p) + p) % p; }
long long mmod() { return 1ll; } template<typename T, typename ...U> long long mmod(const T & head, const U &... tail) { return mod((head % MOD) * mmod(tail...), MOD); }
|
使用方法long long res = mmod(a, b, c, d);
。
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| #include<bits/stdc++.h> using namespace std;
struct Seive { int maxn; vector<bool> isp; vector<int> p, phi;
Seive(int n = 0) : maxn(n), isp(n + 5), phi(n + 5) { for (int i = 0; i < n + 5; i++) { isp[i] = true; phi[i] = 0; } solve(); }
void solve() { isp[0] = isp[1] = false; phi[1] = 1; for (int i = 2; i <= maxn; i++) { if (isp[i]) p.push_back(i), phi[i] = i - 1; for (int j = 0; j < (int)p.size() && i * p[j] <= maxn; j++) { isp[i * p[j]] = false; if (i % p[j]) { phi[i * p[j]] = phi[i] * (p[j] - 1); } else { phi[i * p[j]] = phi[i] * p[j]; break; } } } } };
const long long MOD = 998244353ll; long long mod(long long x, long long p = MOD) { return ((x % p) + p) % p; } long long mmod() { return 1ll; } template <typename T, typename... U> long long mmod(const T &head, const U &... tail) { return mod((head % MOD) * mmod(tail...), MOD); }
int main() { #ifdef ONLINE_JUDGE ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl '\n' #endif
Seive o(1000005);
long long n, k; cin >> n >> k;
long long ans = mmod(n, n + 1, 499122177ll); for(int i = 1; i < k; i++) { ans = mod(ans - (n / i) % MOD * o.phi[i] % MOD, MOD); }
vector<long long>v1(k + 1), v2(k + 1); for(int i = 1; i < k + 1; i++) { v1[i] = v2[i] = n - k + i; } for(auto &x: o.p) { for(long long m = (n - k) / x * x + x; m <= n; m += x) { v1[m - (n - k)] -= v1[m - (n - k)] / x; while(v2[m - (n - k)] % x == 0) { v2[m - (n - k)] /= x; } } } for(int i = 1; i < k + 1; i++) { if(v2[i] > 1) { v1[i] -= v1[i] / v2[i]; } } for(long long i = n - k + 1; i <= n; i++) { ans = mod(ans - (v1[i - (n - k)] % MOD) * (n / i) % MOD, MOD); } cout << ans << endl; }
|
回到开头