hdu - 5528

Posted by WildCow on September 9, 2018

Count a * b

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)

Description

Marry likes to count the number of ways to choose two non-negative integers $a$ and $b$ less than $m$ to make $a×b \pmod m≠0$.

Let’s denote $f(m)$ as the number of ways to choose two non-negative integers $a$ and $b$ less than $m$ to make $a×b \pmod m≠0$.

She has calculated a lot of $f(m)$ for different $m$, and now she is interested in another function $g(n)=∑_{m|n}f(m)$. For example, $g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26$. She needs you to double check the answer.

avater

Give you n. Your task is to find $g(n) \pmod {2^{64}}$

Input

The first line contains an integer T indicating the total number of test cases. Each test case is a line with a positive integer n.

$1≤T≤20000$ $1≤n≤10^9$

Output

For each test case, print one integer s, representing $g(n) \pmod {2^{64}}$

Sample Input

2
6
514

Sample Output

26
328194


定义 $f(n)$ 为选两个 $[0, n)$ 的整数 $a, b$,且 $ab$ 不是 $n$ 的倍数的方案数
然后求一个 $g(n)=∑_{d|n}f(d)$

首先很容易能想到一个容斥
$ab$ 不是 $n$ 的倍数的方案数 = 所有方案数$(n * n)$ - $ab$ 是 $n$ 的倍数的方案数

现在考虑如何表示 $\sum_{a = 0}^{n - 1}\sum_{b = 0}^{n - 1}[n | a·b]$
显然等价于 $\sum_{a = 1}^{n}\sum_{b = 1}^{n}[n | a·b]$

按照常规套路我们令 $t = gcd(a,n)$
那么我们有 $\sum_{a = 1}^{n}\sum_{b = 1}^{n}[n | a·b] \Rightarrow \sum_{a = 1}^{n}\sum_{b = 1}^{n}[n/t | a/t·b]$
这个时候有 $gcd(a/t,n/t) == 1$
即 $a/t$ 对整除 $n/t$ 没有影响
那么我们有 $\sum_{a = 1}^{n}\sum_{b = 1}^{n}[n | a·b] \Rightarrow \sum_{a = 1}^{n}\sum_{b = 1}^{n}[n/t |b]$
也就是在问你 $[1, n]$ 中有多少个能整除 $n / t$
那就是 $n / (n / t) = t$
所以小结一下有 $\sum_{a = 0}^{n - 1}\sum_{b = 0}^{n - 1}[n | a·b]\Rightarrow\sum_{a = 1}^{n}\gcd(a, n)$

接下来
显然对于 $a \in [1, n]$ 有 $gcd(a, n) | n$
即 $gcd(a, n)$ 一定为 $n$ 的因子
所以我们枚举 $n$ 的因子
对于每种因子 $d$
对答案的贡献为 $d · \sum_{a = 1}^{n}[gcd(a, n) == d]$
喜闻乐见的有 $d · \sum_{a = 1}^{n} [gcd(a, n) == d] \Rightarrow d · \sum_{a = 1}^{n}[d | a] · [gcd(a/d, n/d) == 1]$
那么因为 $d|a$ ,所以 $a / d$ 一定是个整数
所以我们枚举 $a / d$
有 $d · \sum_{a = 1}^{n} [gcd(a, n) == d] \Rightarrow d · \sum_{i = 1}^{n / d}[gcd(i, n/d) == 1]​$
我们会惊讶的发现(???)$\phi(n/d) = \sum_{i = 1}^{n / d}[gcd(i, n/d) == 1]$
因此再小结一下我们有 $\sum_{a = 1}^{n}\gcd(a, n)\Rightarrow \sum_{d|n}^{n}d · \phi(n/d)$
因此 $f(n) = n^2 - \sum_{d|n}^{n}d · \phi(n/d)$

到这里有一个感觉还不错的式子了
但是时间复杂度还是不太行

为了方便表示我们设 $h(n) = \sum_{d|n}^{n}d · \phi(n/d)$
那么 $h(n)$ 是 $a(n) = n$ 和 $\phi(n)$ 的迪利克雷卷积
所以 $h(n)$ 为积性函数
则 $f(n) = n^2 - h(n)$

那么 $g(n) = \sum_{d|n}d^2 - \sum∑_{d|n}h(d)$

现在我们来看 $\sum_{d|n}h(d)$ 的部分
即 $\sum_{d|n}\sum_{x|d}^{d}x · \phi(d/x)$
我们尝试交换一下枚举顺序,先枚举 $x$
对于第二层循环我们会惊讶的发现我们可以直接枚举 $d / x$
那么我们就有 $\sum_{d|n}\sum_{x|d}^{d}x · \phi(d/x)\Rightarrow \sum_{d|n} d · \sum_{i | \frac{n}{d}}^{d}\phi(i)$
都 8102 年了应该没人不知道 $\sum_{i | \frac{n}{d}}^{d}\phi(i) = \frac{n}{d}$ 了吧
不过还是可以证一下

一般的,我们证明,$n = \sum_{d|n} \phi(d)$
即一个数因子的欧拉函数和等于他自身

这里采用离散数学的证明方式
对于一个数 $n$,我们考虑他的因子用 $d_1, d_2, …,d_m$ 表示
对于第 $i$ 个因子,显然和他互质的数字有 $\phi(d_i)$ 个
我们表示为 $p_{i,1}, p_{i, 2}, …, p_{i, \phi(i)}$

于是我们定义集合 $A = {(p_{i, j}, d_i)|(p_{i, j}, d_i),(i = 1, 2, …, m; j = 1, 2,…, \phi(d_i))}$
定义集合 $B = {1, 2, …, n}$
显然集合 $A$ 内元素的个数就是 $\sum_{d|n} \phi(d)$ 的结果
如果 $A, B$ 这两个集合一一对应
那么就说明这两个集合内的元素是一样多的
即 $n = \sum_{d|n} \phi(d)$

定义一个映射 $f(A \rightarrow B): (p_{i, j}, d_i) \rightarrow p_{i, j} · \frac{n}{d_i}$
首先来看这个映射后的数据范围
显然有 $1 ≤ p_{i, j} ≤ d_i$
所以显然 $1 ≤ p_{i, j} · \frac{n}{d_i} ≤ n$
接下来我们需要证明这个映射是一个双射,即一一对应

  • 单射

    单射即要证明对于 $A$ 中的不同元素也会映射成 $B$ 中的不同元素
    我们还是分情况讨论

    • 对于相同因子的不同互质数,即$(p_{i, j’}, d_i)$ 和 $(p_{i, j}, d_i)$
      这个显然 $p_{i, j’} · \frac{n}{d_i} \not= p_{i, j} · \frac{n}{d_i}$
    • 对于不同因子 $d_i \not= d_j$
      我们采取反证法假设有 $p_{i, a} · \frac{n}{d_i} = p_{j, b} · \frac{n}{d_j}$
      等式两边化简一个 $n$ 然后移项有 $p_{i, a} · d_j = p_{j, b} · {d_i}$
      然后是 $\frac{p_{i, a} · d_j}{p_{j, b} · {d_i}} = 1$
      因为 $p_{i, a}$ 和 $d_i$ 互质
      所以有 $p_{j, b} | p_{i, a}$
      同理对于 $\frac{p_{j, b} · d_i}{p_{i, a} · {d_j}} = 1$
      我们有 $p_{i, a} | p_{j, b}$
      综上我们有 $p_{i, a} = p_{j, b}$
      那么就要有 $d_i = d_j$
      与已知相矛盾

    证毕

  • 满射

    即 $B$ 中任意元素都能在 $A$ 中找到
    那么我们对于 $B$ 中任意元素 $t$
    令 $d = gcd(t, n)$
    那么老套路有 $gcd(t / d, n / d) == 1$
    即 $(t / d, n / d)$ 对应为 $A$ 的一个元素
    证毕

所以 $f$ 为 $A \rightarrow B$ 的一个双射函数
即 $n = \sum_{d|n} \phi(d)$

那么如今我们已经化成了 $ g(n) = ∑_{d|n}d^2 - n×\tau(n)$

我们有理由相信 $A(x) = \sum_{d|n}d^2$ 是一个积性函数
其实 $B(x) = \sum_{d|n}d^k$ 都是积性函数
所以我们只需要考虑对于 $n =p^{\alpha}$ 的情况
那么我们直接有 $\sum_{d|n}d^2 = p^0 + p^2 + … + p^{2\alpha}$
这显然是一个公比为 $p^2$ 的等差数列
那就直接有 $\sum_{d|n}d^2 = \frac{p^{2\alpha + 2} - 1}{p^2 - 1}$
根据积性函数的性质
最终我们有 $g(n) = \prod \frac{(p_i^{\alpha_i + 1})^2 - 1}{p_i^2 - 1} - n \prod(\alpha_i + 1)$

虽然代码跑得慢,但毕竟是亲生的嘿嘿嘿


#include <bits/stdc++.h>
#define LL unsigned long long
using namespace std;

const int N = 100010;

int pri[N];
bool vis[N];
int num;

int Ini()
{
    int i, q;
    num = 0;

    memset(vis, 0, sizeof(vis));
    for(i = 2, q = sqrt(N) + 1; i < q; i ++){
        if(!vis[i]){
            pri[num] = i;
            num ++;
            for(int j = i << 1; j < N; j += i){
                vis[j] = true;
            }
        }
    }
    for(; i < N; i ++){
        if(!vis[i]){
            pri[num] = i;
            num ++;
        }
    }
}

int main(int argc, char const *argv[])
{
    int ncase;
    int cnt;
    LL n;
    LL t, q;
    LL ans1, ans2;
    LL a, b, c;

    Ini();
    scanf("%d", &ncase);
    while(ncase --){
        cin >> n;
        ans1 = 1;
        ans2 = n;
        for(int i = 0; i < num; i ++){
            if(pri[i] * pri[i] > n){
                break;
            }
            if(n % pri[i] == 0){
//                cout << ans1 << endl;
//                cout << ans2 << endl;
                cnt = 1;
                t = pri[i];
                q = pri[i] * pri[i] - 1;
                while(n % pri[i] == 0){
                    n /= pri[i];
                    cnt ++;
                    t *= pri[i];
                }
                a = (t - 1) / (pri[i] - 1);
                b = t + 1;
                c = pri[i] + 1;
                if(a % c == 0){
                    ans1 *= a / c * b;
                }
                else{
                    ans1 *= b / c * a;
                }
                ans2 *= cnt;
            }
        }
        if(n > 1){
            ans2 *= 2;
            ans1 *= (1 + n * n);
        }
//        cout << ans1 << endl;
//        cout << ans2 << endl;
        cout << ans1 - ans2 << endl;
    }

    return 0;
}
```