题解

4 条题解

  • 2
    @ 2016-08-03 23:48:57

    由于\(NM\)的约数一定可以写成\(\frac{pM} {q}(p \mid N ,q \mid M)\)的形式,我们有:
    \[d(NM)=\sum_{p\mid N}\sum_{q\mid M}[\gcd(p,q)=1]\]
    代入原式:
    \[\begin{aligned}\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)&=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{p \mid i}\sum_{q \mid j}[\gcd(p,q)=1] \\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}\left \lfloor \frac {N} {i} \right \rfloor \left \lfloor \frac {M} {j} \right \rfloor[\gcd(i,j)=1] \\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}\left \lfloor \frac {N} {i} \right \rfloor \left \lfloor \frac {M} {j} \right \rfloor\sum_{d \mid \gcd(i,j)}\mu(d) \\ &=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor }\left \lfloor\frac{N}{id}\right\rfloor\left \lfloor\frac{M}{jd}\right\rfloor \\ &=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor} \left \lfloor\frac{N}{id}\right\rfloor\sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor }\left \lfloor\frac{M}{jd}\right\rfloor\end{aligned}\]
    设\(g(n)=\sum_{i=1}^{n}\left \lfloor \frac {n} {i}\right \rfloor\),于是
    \[\begin{aligned}\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)&=\sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\left \lfloor \frac {N} {d} \right \rfloor} \left \lfloor\frac{\left \lfloor\frac{N}{d}\right\rfloor}{i}\right\rfloor \sum_{j=1}^{\left \lfloor \frac {M} {d} \right \rfloor} \left \lfloor\frac{\left \lfloor\frac{M}{d}\right\rfloor}{j}\right\rfloor\\&=\sum_{d=1}^{N}\mu(d)g(\left \lfloor\frac{N}{d}\right \rfloor) g(\left \lfloor\frac{M}{d}\right\rfloor)\end{aligned}\]
    注意到\(g\)是\(d\)的前缀和,而\(d\)是积性函数,可以线性筛出\(d\)之后预处理出\(g\)。

    之后用分块加速计算就可以了。

    • @ 2017-01-02 10:34:57

      大神似乎打错了一个地方吧
      带入原式的第一步似乎把i和N、j和M给打错了……

    • @ 2017-01-14 16:57:32

      似乎的确错了,已改w

  • 1
    @ 2015-08-04 22:04:00

    约数个数和:枚举gcd的值k。利用mobius变换,统计的结果是mu*一个可以预处理出来的值(关于n/k与m/k的)。然后再发现对于连续的若干个k,这样的结果是相同的。所以只要把k的考虑一块一块来,似乎蛮简单的。

  • 0
    @ 2016-09-17 16:44:22

    AC代码:
    ```c++
    测试数据 #0: Accepted, time = 31 ms, mem = 1584 KiB, score = 10
    测试数据 #1: Accepted, time = 46 ms, mem = 1588 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1584 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1584 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
    测试数据 #7: Accepted, time = 593 ms, mem = 1588 KiB, score = 10
    测试数据 #8: Accepted, time = 546 ms, mem = 1588 KiB, score = 10
    测试数据 #9: Accepted, time = 562 ms, mem = 1584 KiB, score = 10
    Accepted, time = 1778 ms, mem = 1588 KiB, score = 100

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #define LL long long
    #define maxn 50001
    using namespace std;
    int tot,prime[30001],mu[maxn],c[maxn];
    LL d[maxn],Ans[101][101];
    bool isprime[maxn];

    int gcd(int a,int b) {
    return b?gcd(b,a%b):a;
    }

    void genPrime(int n) {
    memset(isprime,1,sizeof isprime);
    mu[1] = d[1] = c[1] = 1;
    for (int i=2;i<=n;++i) {
    if (isprime[i]) {
    prime[tot++] = i;
    mu[i] = -1;
    c[i] = 1;
    d[i] = 2;
    }
    for (int j=0;j<tot && i*prime[j]<=n;++j) {
    isprime[i*prime[j]] = 0;
    if (i%prime[j] == 0) {
    d[i*prime[j]] = d[i]/(c[i] + 1)*(c[i] + 2);
    c[i*prime[j]] = c[i] + 1;
    break;
    }
    mu[i*prime[j]] = -mu[i];
    d[i*prime[j]] = d[i] * d[prime[j]];
    c[i*prime[j]] = 1;
    }
    }
    for (int i=1;i<=n;++i) mu[i] += mu[i-1];
    for (int i=1;i<=n;++i) d[i] += d[i-1];
    }

    inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48,ch = getchar();
    return x;
    }

    char a[18];

    inline void print(LL x) {
    a[0] = 0;
    while (x) a[++a[0]] = x%10,x/=10;
    for (;a[0];--a[0])
    putchar(a[a[0]]+48);
    putchar('\n');
    }

    int main() {
    genPrime(50000);
    int t = read();
    while (t--) {
    int n = read(),m = read();
    if (n <= 100 && m <= 100) {
    if (Ans[n][m]) {
    print(Ans[n][m]);
    continue;
    }
    }
    if (n > m) swap(n,m);
    LL ans = 0;
    for (int i=1,nex;i<=n;i=nex+1) {
    nex = min(n/(n/i),m/(m/i));
    ans += (mu[nex] - mu[i-1]) * d[n/i] * d[m/i];
    }
    if (n<=100 && m<=100) Ans[n][m] = Ans[m][n] = ans;
    print(ans);
    }
    return 0;
    }
    ```

  • 0
    @ 2015-10-02 09:23:22

    *Doc你太深奥了,看不懂
    *能贴部分类似mobius的代码吗
    *大概K要怎么计算
    *谢谢

  • 1

信息

ID
1949
难度
6
分类
(无)
标签
递交数
99
已通过
28
通过率
28%
上传者