- T = 10000
- N, M <= 10000000
- Solution
最近开始狂补东西
莫比乌斯反演就是之一, 然后做题
个人认为反演里要设计出 F(x) 和 f(x) 是有难度的, 其他大佬们都说做多了就是套路了, 所以还欠火候, 加紧做题
对于这道题, 我们设 F(d) 为 gcd 为 d 及其倍数的对数的个数, 设 f(x) 为 gcd 为 d 的对数的个数
那么我们有
进行反演
那么需要求的就是 (p 为质数, 小于等于 N 也小于等于 M)
改变枚举顺序, 把枚举 p 的倍数变成枚举上式的 d/p
并且因为
式子变为
我们令 T=dp, 把枚举 d 变为枚举 T, 同时把后边的两个分式提出来
发现后面的可以在素数筛的时候预处理, 那么对于一组数据就可做了
对于多组数据, 我们发现这个式子是可以整除分块的, 优化后就可以过了
对于预处理, 我们设一个 g(T)
素数筛的时候, 令 k=i*prime[j]
1) 如果 prime[j] 整除 i,mu[k]=0
2) 如果不整除, 那么根据定义, mu[k]=-mu[i]
因为筛中每个数只会筛到一次, 所以赋值之后就不会再被覆盖
由于之前用了整除分块, 所以 g 还需要一个数组 s 存前缀和, 分块时就可以直接把值拿出来了
- #include < bits / stdc++.h > #define ll long long const int MAXN = 10000000 + 10;
- ll T,
- prime[MAXN],
- cnt,
- g[MAXN],
- s[MAXN],
- mu[MAXN];
- bool vis[MAXN];
- template < typename T > inline void read(T & x) {
- T data = 0,
- w = 1;
- char ch = 0;
- while (ch != - && (ch < 0 || ch > 9)) ch = getchar();
- if (ch == - ) w = -1,
- ch = getchar();
- while (ch >= 0 && ch <= 9) data = ((T) data << 3) + ((T) data << 1) + (ch ^ 0),
- ch = getchar();
- x = data * w;
- }
- template < typename T > inline void write(T x, char c = \0) {
- if (x < 0) putchar( - ),
- x = -x;
- if (x > 9) write(x / 10);
- putchar(x % 10 + 0);
- if (c != \0) putchar(c);
- }
- template < typename T > inline void chkmin(T & x, T y) {
- x = (y < x ? y: x);
- }
- template < typename T > inline void chkmax(T & x, T y) {
- x = (y > x ? y: x);
- }
- template < typename T > inline T min(T x, T y) {
- return x < y ? x: y;
- }
- template < typename T > inline T max(T x, T y) {
- return x > y ? x: y;
- }
- inline void init() {
- memset(vis, true, sizeof(vis));
- vis[0] = vis[1] = 0;
- mu[1] = 1;
- for (register int i = 2; i < MAXN; ++i) {
- if (vis[i]) {
- prime[++cnt] = i;
- mu[i] = -1;
- }
- for (register int j = 1; j <= cnt && i * prime[j] < MAXN; ++j) {
- vis[i * prime[j]] = 0;
- if (i % prime[j]) mu[i * prime[j]] = -mu[i];
- else break;
- }
- }
- for (register int j = 1; j <= cnt; ++j) for (register int i = 1; i * prime[j] < MAXN; ++i) g[i * prime[j]] += mu[i];
- for (register int i = 1; i < MAXN; ++i) s[i] = s[i - 1] + g[i];
- }
- inline ll solve(ll N, ll M) {
- ll ans = 0;
- for (register int i = 1;;) {
- if (i > min(N, M)) break;
- ll j = min(N / (N / i), M / (M / i));
- ans += (N / i) * (M / i) * (s[j] - s[i - 1]);
- i = j + 1;
- }
- return ans;
- }
- int main() {
- init();
- read(T);
- while (T--) {
- ll N,
- M;
- read(N);
- read(M);
- write(solve(N, M), \n);
- }
- return 0;
- }
2820 YY 的 GCD
来源: http://www.bubuko.com/infodetail-2520912.html