[传送门] http://acm.hdu.edu.cn/showproblem.php?pid=6588
求 $$\sum_{i=1}^{n} \gcd(\lfloor \sqrt[3]{i} \rfloor, i)$$
题解写的很清楚, 自己重新推一推.
- $$\sum_{
- i=1
- }^{
- n
- } \gcd(\lfloor \sqrt[3]{
- i
- } \rfloor, i)$$
- $$=\sum_{
- a=1
- }^{
- \lfloor\sqrt[3]{
- n
- }\rfloor
- }\sum_{
- i=1
- }^{
- n
- }\gcd(a, i)[\sqrt[3]{
- i
- }=a]$$
- $$=\sum_{
- a=1
- }^{
- \lfloor\sqrt[3]{
- n
- }\rfloor
- }\sum_{
- i=a^3
- }^{
- \min\{
- (a+1)^3-1,n\
- }
- }\gcd(a,i)$$
- $$=\sum_{
- i=\lfloor \sqrt[3]{
- n
- } \rfloor ^3
- }^{
- n
- }\gcd(\sqrt[3]{
- n
- }, i)+\sum_{
- a=1
- }^{
- r
- }\sum_{
- i=a^3
- }^{
- (a+1)^3-1
- }\gcd(a,i)$$
其中 $r = \sqrt[3]{n}-1$
设 $f(n,a)=\sum_{i=1}^{n}\gcd(i, a)$
- $$f(n,a)=\sum_{
- i=1
- }^{
- n
- }\gcd(i,a)$$
- $$=\sum_{
- d|a
- }d\sum_{
- i=1
- }^{
- n
- }[\gcd(i,a)=d]$$
- $$=\sum_{
- d|a
- }d\sum_{
- i=1
- }^{
- \lfloor \frac{
- n
- }{
- d
- } \rfloor
- }[\gcd(i, \frac{
- a
- }{
- d
- }) =1]$$
- $$=\sum_{
- d|a
- }d\sum_{
- i=1
- }^{
- \lfloor \frac{
- n
- }{
- d
- } \rfloor
- }\sum_{
- p|\gcd(i,\frac{
- a
- }{
- d
- })
- }\mu(p)$$
- $$=\sum_{
- d|a
- }d\sum_{
- p|\frac{
- a
- }{
- d
- }
- }\mu(p)\sum_{
- i=1
- }^{
- \lfloor \frac{
- n
- }{
- d
- } \rfloor
- }[p|i]$$
- $$=\sum_{
- d|a
- }d\sum_{
- p|\frac{
- a
- }{
- d
- }
- }\mu(p)\lfloor \frac{
- n
- }{
- pd
- } \rfloor$$
- $$=\sum_{
- T|a
- }\lfloor \frac{
- n
- }{
- T
- }\rfloor\sum_{
- p|T
- }\mu(p)\frac{
- T
- }{
- p
- }$$
- $$=\sum_{
- T|a
- }\lfloor \frac{
- n
- }{
- T
- }\rfloor \varphi(T)$$
第一部分可以 $O(\sqrt{n})$ 解决.
将 $f(n, a)$ 带入第二部分得
- $$\sum_{
- a=1
- }^r \sum_{
- i=a
- }^{
- (a+1)^3-1
- }\gcd(a,i)$$
- $$=\sum_{
- a=1
- }^{
- r
- }\sum_{
- T|a
- }(\lfloor\frac{
- (a+1)^3-1
- }{
- T
- }\rfloor - \lfloor\frac{
- a^3-1
- }{
- T
- }\rfloor)\varphi(T)$$
- $$=\sum_{
- T = 1
- }^{
- r
- }\varphi(T)\sum_{
- b=1
- }^{
- \lfloor\frac{
- r
- }{
- T
- }\rfloor
- }(\lfloor\frac{
- (bT+1)^3-1
- }{
- T
- } \rfloor-\lfloor\frac{
- (bT)^3-1
- }{
- T
- } \rfloor)$$
- $$=\sum_{
- T=1
- }^{
- r
- }\varphi(T)\sum_{
- b=1
- }^{
- \lfloor\frac{
- r
- }{
- T
- }\rfloor
- }(\lfloor b^3T^2+3b^2T+3b\rfloor-\lfloor b^3T^2-\frac{
- 1
- }{
- T
- }\rfloor)$$
- $$=\sum_{
- T=1
- }^{
- r
- }\varphi(T)\sum_{
- b=1
- }^{
- \lfloor\frac{
- r
- }{
- T
- }\rfloor
- }(3b^2T+3b+1)$$
- $$=\sum_{
- T=1
- }^{
- r
- }\varphi(T)(3T\sum_{
- b=1
- }^{
- \lfloor\frac{
- r
- }{
- T
- }\rfloor
- }b^2+3\sum_{
- b=1
- }^{
- \lfloor\frac{
- r
- }{
- T
- }\rfloor
- }b + \lfloor\frac{
- r
- }{
- T
- }\rfloor)$$
这部分 $O(r)$ 解决.
用太多 int128 会 T.
- #include <bits/stdc++.h>
- namespace IO {
- void read() {}
- template <typename T, typename... T2>
- inline void read(T &x, T2 &... oth) {
- T f = 1; x = 0;
- char ch = getchar();
- while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
- while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
- x *= f;
- read(oth...);
- }
- }
- #define read IO::read
- #define print IO::print
- #define ll long long
- #define int128 __int128
- const int MOD = 998244353;
- const int inv6 = 166374059, inv2 = 499122177;
- const int N = 1e7 + 7;
- int prime[N], phi[N], prin;
- bool vis[N];
- void init() {
- phi[1] = 1;
- for (int i = 2; i <N; i++) {
- if (!vis[i]) { prime[++prin] = i; phi[i] = i - 1; }
- for (int j = 1; j <= prin && i * prime[j] < N; j++) {
- vis[i * prime[j]] = 1;
- if (i % prime[j] == 0) {
- phi[i * prime[j]] = prime[j] * phi[i];
- break;
- }
- phi[i * prime[j]] = phi[i] * phi[prime[j]];
- }
- }
- }
- int root3(int128 n) {
- int l = 1, r = 1e7 + 7;
- int ans = 1;
- while (l <= r) {
- int128 mid = (l + r) / 2;
- if (mid * mid * mid <= n) l = mid + 1, ans = mid;
- else r = mid - 1;
- }
- return ans;
- }
- template<class T>
- T gcd(T a, T b) {
- while (b) {
- a %= b;
- std::swap(a, b);
- }
- return a;
- }
- void M(int &a) {
- if (a <0) a += MOD;
- if (a>= MOD) a -= MOD;
- }
- int f(int128 n, int a) {
- int ans = 0;
- for (int i = 1; 1LL * i * i <= a; i++) {
- if (a % i) continue;
- int128 temp = n / i * phi[i] % MOD;
- M(ans += temp);
- if (a == i * i) continue;
- int j = a / i;
- temp = n / j * phi[j] % MOD;
- M(ans += temp);
- }
- return ans;
- }
- int sum_squr(int n) {
- int ans = 1LL * n * (n + 1) % MOD * (2 * n + 1) % MOD * inv6 % MOD;
- return ans;
- }
- int sum(int n) {
- return 1LL * n * (n + 1) / 2 % MOD;
- }
- int main() {
- init();
- int T;
- read(T);
- while (T--) {
- int128 n;
- read(n);
- if (n <= 7) {
- int ans = 0;
- for (int i = 1; i <= n; i++)
- ans += gcd(1, i);
- printf("%d\n", ans);
- continue;
- }
- int r = root3(n);
- int128 rr = (int128)r * r * r;
- int ans = f(n, r) - f(rr - 1, r);
- M(ans);
- r--;
- for (int i = 1; i <= r; i++) {
- int y = r / i;
- int temp = 3LL * i * sum_squr(y) % MOD;
- M(temp += 3LL * sum(y) % MOD);
- M(temp += y);
- temp = 1LL * temp * phi[i] % MOD;
- M(ans += temp);
- }
- printf("%d\n", ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3303001.html