前置知识 整数分块
整除分块是用于快速处理形似 的式子的方法 很显然,这个可以O (n )得到答案。但是,在某些题目中,毒瘤出题人将数据加强到了 以上,这个时候我们就无法通过O (n )的解法来得到答案了。我们需要一个的更为优秀的解法 首先观察这个式子,找几个特殊值代入n=5时,sum=5+2+1+1+1
可以发现的是:(这里给的例子并不明显,其实应该找一个大的n来代入才直观,读者可以自行尝试) 对于单一的,某些地方的值是相同的,并且呈块状分布 通过进一步的探求规律与推理以及打表与瞎猜,我们可以惊喜的发现一个规律,这些块状分布的值是有规律的 对于一个块,假设它的起始位置的下标为l,那么可以得到的是,它的结束位置的下标为 如果实在看的有点懵逼,可以继续采用代入特殊值的方法,验证一下上方的规律,用程序表现出来即为
1 2 3 4 5 for (int l = 1 , r;l <= n;l = r + 1 ){ r = n / (n / l); ans += (r - l + 1 ) * mu[l]; }
重要函数:
简介
简要证明:
1.直接证
2.运用狄利克雷卷积
如果看不懂的话, 我将1的详细步骤写一下:
我们将原式化简可得
我们令 即可化简的 我们再令 带回原式可得 我们不妨设x = n / d, 则x * d = n, 那么当x确定时,d同样也确定,反之亦然同理, 则f(x)和μ(d)所枚举到的数完全一样,即我们可以交换f(x)和μ(d),那么原式即可变形为 此时我们再联想到S(x), 再令x = n / i, 就可以得到
此时再将F(n)代回
证毕
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #define LL long long using namespace std;const int N = 1e7 + 10 ;int prime[N], cnt, n, phi[N], g[N];bool d[N];LL s[N]; void init () { phi[1 ] = 1 ; for (int i = 2 ;i < N;i ++) { if (!d[i]) prime[++ cnt] = i, phi[i] = - 1 ; for (int j = 1 ;j <= cnt && i * prime[j] < N;j ++) { d[i * prime[j]] = 1 ; if (i % prime[j] == 0 ) { phi[i * prime[j]] = 0 ; break ; } else phi[i * prime[j]] = - phi[i]; } } for (int j = 1 ;j <= cnt;j ++) { for (int i = 1 ;i * prime[j] < N;i ++) { g[i * prime[j]] += phi[i]; } } for (int i = 2 ;i < N;i ++) s[i] = s[i - 1 ] + g[i]; } int T;LL ans; int m;int main () { init (); scanf ("%d" , &T); while (T --) { ans = 0 ; scanf ("%d %d" , &n, &m); if (n > m) swap (n, m); for (int l = 1 , r;l <= n;l = r + 1 ) { r = min (n, min (n / (n / l), m / (m / l))); ans += (s[r] - s[l - 1 ]) * (LL)(n / l) * (m / l); } printf ("%lld\n" , ans); } return 0 ; }