青青青碰碰,爱搞视频网91N

LUOGU 3455
Description
FGD正在破解一段密碼，他需要回答很多類似的問(wèn)題：對(duì)于給定的整數(shù) $a,b$ 和 $d$ ，有多少正整數(shù)對(duì) $x,y$ ，滿足 $x<=a,y<=b$ ，并且 $gcd(x,y)=d$ 。作為FGD的同學(xué)，F(xiàn)GD希望得到你的幫助。

Input Format
第一行一個(gè)正整數(shù) $N$ ，表示詢問(wèn)組數(shù)。
接下來(lái) $N$ 行，每行 $3$ 個(gè)正整數(shù) $a,b,d$ ，含義如題目所示意。

Output Format
對(duì)于每個(gè)詢問(wèn)輸出一行表示答案。

Sample Input

2
4 5 2
6 4 3

Output Format

3
2

Constraints
對(duì)于 $100$ %的數(shù)據(jù)，滿足 $1 \leq N \leq 50000,1 \leq d \leq a,b \leq 50000$ 。

CCYOS
這是一道莫比烏斯反演的板子題。

前置技能

符號(hào)	含義
$a \mid b$	$a$ 被 $b$ 整除
$P$	質(zhì)數(shù)集合
$\omega (n)$	$n$ 的不同質(zhì)因數(shù)個(gè)數(shù)
$\phi (n)$	$[1,n - 1]$ 內(nèi)與n互質(zhì)的數(shù)的個(gè)數(shù)`顯然n和本身不互質(zhì)`
$\mu(u)$	莫比烏斯函數(shù)，詳見(jiàn)下文
$\epsilon$	狄利克雷卷積單位元
$1(n)$	對(duì)于任意 $n \in N*$ ， $1(n) = 1$ ，乘法單位元
$Id(n)$	對(duì)于任意 $n \in N*,Id(n) = n$
$[P]$	命題 $P$ 成立， $[P] = 1$ ；反之為 $0$

概念	含義
數(shù)論函數(shù)	定義域?yàn)槿w正整數(shù)，值域?yàn)閺?fù)數(shù)域子集的函數(shù)。
積性函數(shù)	若 $gcd(a,b) = 1$ ，則 $f(a) \times f(b) = f(ab)$
完全積性函數(shù)	對(duì)于任意 $a,b$ ，都有 $f(a) \times f(b) = f(ab)$

莫比烏斯函數(shù)
$\mu(n) = \begin{cases} 1………… n = 1 \\ (-1)^{\omega(n)} …\forall k_i = 1\\ 0 …………other \end{cases}$ 其中， $k_i$ 表示每一個(gè)質(zhì)因數(shù)的次數(shù)。 $n = p_1^{k_1}·p_2^{k_2}·……·p_{\omega(n)}^{k_{\omega(n)}}$
一個(gè)重要的性質(zhì) $\sum_{d \mid n}\mu(d) = [n = 1]$

證明如下：
1）當(dāng) $n = 1$ 時(shí):顯然 $[n = 1] = 1$ ?？擅杜e的約數(shù) $d$ 只有 $1$ ，則原式 = $\mu(1)$ = $1$ = $[ n = 1]$ 。
2）當(dāng) $\forall k_i = 1$ 時(shí):顯然此時(shí) $n > 0$ ， $[n = 1] = 0$ 。 $n = p_1^{k_1}·p_2^{k_2}·……·p_{\omega(n)}^{k_{\omega(n)}}$ 則約數(shù) $d = p_1^{k'_1}·p_2^{k'_2}·……·p_{\omega(n)}^{k'_{\omega(n)}}$ 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cforall%20k_i%20%3D%201" alt="\forall k_i = 1" mathimg="1">，所以 $\forall k'_i \in [0,1]$ 。不難看出，枚舉 $n$ 的約數(shù)，即枚舉取的質(zhì)因數(shù)的乘積即可。根據(jù) $\mu$ 的定義，有 $\sum_{d \mid n} \mu(d) = \sum_{i = 1}^{\omega(n)} C_{\omega(n)} ^ {i} · (-1)^i$ 根據(jù)二項(xiàng)式定理 $(x + y)^k = \sum_{i = 0}^{n}C_{n}^{i}·x^iy^{n - i}$ 構(gòu)造可得 $\sum_{d \mid n} \mu(d) = \sum_{i = 1}^{\omega(n)} C_{\omega(n)} ^ {i} · (-1)^i·1^{n - i} = (1 - 1)^{\omega(n)} = 0$ 即此時(shí)原式恒為0。
3）定義域內(nèi) $(n > 0)$ 其他情況:即在第二種情況上添加 $add = \sum\mu(d),d|n且\exists k'_i > 1$ ，據(jù)定義有 $add = 0$ 。所以此時(shí)原式恒為0。
證畢。

get_mu函數(shù)的寫法

inline void get_mu(int N){
    miu[1] = 1;//初始化
    for(int i = 2;i <= N;++i){//從2開(kāi)始
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;//標(biāo)記質(zhì)數(shù)，質(zhì)數(shù)只有兩個(gè)約數(shù)所以質(zhì)數(shù)的miu值一定是-1
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;//標(biāo)記合數(shù)
            if(!(i % prime[j]))break;//避免標(biāo)記到存在ki >= 2的數(shù)
            else miu[i * prime[j]] = -miu[i];//多了一個(gè)質(zhì)因數(shù),(-1)^k要取相反
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];//前綴和便于計(jì)算
}

狄利克雷卷積
$f*g = \sum_{d \mid n}f(d) · g(\frac{n}u0z1t8os)$ 滿足交換率，結(jié)合率，分配律。
兩個(gè)積性函數(shù)的卷積一定是積性函數(shù)。

$\mu * 1 = \epsilon$
單位元 $\epsilon$ 的是滿足 f * e = f的函數(shù)，當(dāng) e = [n = 1]時(shí)，這個(gè)條件成立，所以這種定義是滿足條件的定義之一。而且很好記。

證明： $\mu * 1 = \sum_{d \mid n}\mu(d)·1(\frac{n}u0z1t8os) = \sum_{d \mid n}\mu(d) = [n = 1] = \epsilon$
證畢

歐拉函數(shù)
一個(gè)重要的性質(zhì)
$\sum_{d \mid n} \varphi(d) = n$

證明：
咕咕咕。不會(huì)證。

推論
1） $\phi * 1 = Id$

證明：
$Id(n) = n = \sum_{d \mid n} \phi(d) = \sum_{d \mid n} \phi(d)·1(\frac{n}u0z1t8os) = 1 * \phi$ 證畢

2） $\phi = Id * \mu$

證明：
由5.1.推出 $\phi * 1 * \mu= Id * \mu$ 狄利克雷卷積滿足結(jié)合律，所以 $\phi *( 1*\mu) = Id * \mu$ 由4.可得 $\phi * \epsilon = Id * \mu = \phi$ 證畢

莫比烏斯反演
當(dāng) $f(n) = \sum_{d \mid n}g(d)$ 必然有 $g(n) = \sum_{d \mid n}f(\frac{n}u0z1t8os)·\mu(d)$ 假設(shè)和結(jié)果互換，此仍然為真命題。

證明如下：
構(gòu)造轉(zhuǎn)化假設(shè)，有 $f(n) = \sum_{d \mid n}g(d)·1(\frac{n}u0z1t8os) = g*1$
則轉(zhuǎn)為證明：若 $f = g*1,$ 則 $g = f * \mu$ 。
與5.2.證明相類似，由假設(shè)得到 $f*\mu = g * (1 * \mu)$ 由4.得 $f * \mu = g * \epsilon = g$
反之證若 $g = f * \mu,$ 則 $f = g*1$ : $g * 1 = f * (u * 1)$ $g * 1 = f * \epsilon$ $g * 1 = f$ 證畢

一些常見(jiàn)的推論
1） $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_u0z1t8os\mu(d)·\lfloor \frac{n}u0z1t8os \rfloor · \lfloor \frac{m}u0z1t8os \rfloor$

證明:
由莫比烏斯函數(shù)的性質(zhì)可得 $[gcd(i,j) = 1] = \sum_{d \mid gcd(i,j)}\mu(d)$ 代入原式可得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_{i}\sum_{j}\sum_{d \mid gcd(i,j)}\mu(d)$ 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=d%20%5Cmid%20gcd(i%2Cj)" alt="d \mid gcd(i,j)" mathimg="1">，所以 $d \mid i,d \mid j$ ，故考慮先枚舉 $d$ ，再枚舉 $i,j$ ，可得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_u0z1t8os\mu(d)\sum_{i}^{\lfloor \frac{n}u0z1t8os \rfloor}\sum_{j}^{\lfloor \frac{m}u0z1t8os \rfloor}1$ 把后面一段廢話化簡(jiǎn)得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_u0z1t8os\mu(d)·\lfloor \frac{n}u0z1t8os \rfloor · \lfloor \frac{m}u0z1t8os \rfloor$ 證畢

2） $\sum_{i}\sum_{j}[gcd(i,j) = k] = \sum_u0z1t8os\mu(d)·\lfloor \frac{n}{kd} \rfloor · \lfloor \frac{m}{kd} \rfloor$

證明：
將原式轉(zhuǎn)化為 $\sum_{i}\sum_{j}[gcd(\frac{i}{k},\frac{j}{k}) = 1]$ 依照6.1.的證明。
證畢

3） $\sum_{i}\sum_{j}gcd(i,j) = \sum_u0z1t8os\phi(d)·\lfloor \frac{n}u0z1t8os \rfloor · \lfloor \frac{m}u0z1t8os \rfloor$

證明：
由5.1可得 $Id(gcd(i,j)) = \sum_{d \mid gcd(i,j)}\phi(d) · 1(\frac{gcd(i,j)}u0z1t8os) =\sum_{d \mid gcd(i,j)}\phi(d)$ 代入原式中可得 $\sum_{i}\sum_{j}gcd(i,j) = \sum_{i}\sum_{j}\sum_{d \mid gcd(i,j)}\phi(d)$ 依照6.1.證明。
證畢

一般做法
根據(jù)題意列出算式。
列出一個(gè)可以反演的方程。
反復(fù)化簡(jiǎn)，向 $\mu$ 函數(shù)靠攏。
計(jì)算。

小技巧：整除分塊
通過(guò)觀（da）察（biao）發(fā)現(xiàn)，在處理 $\sum_{i}\frac{n}{i}$ 的過(guò)程中，會(huì)出現(xiàn)很多相同的結(jié)果，而且這些結(jié)果呈塊狀分布。進(jìn)一步觀（da）察（biao），會(huì)發(fā)現(xiàn)對(duì)于每一個(gè)結(jié)果相同的塊，當(dāng)前位置為 $i$ ,這個(gè)塊的結(jié)束位置為 $\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$ 。
那么整除分塊的代碼就很好寫了：

for(int l = 1,r;l <= n;l = r + 1){
  r = n/(n/l);  
  一些操作;
}

在GC的幫助下找到了理解這個(gè)問(wèn)題的另一個(gè)思路：LUOGU 1403 感謝?。。?/p>

code

#include<bits/stdc++.h>
using namespace std;

#define mxn 50005
int N,cnt;
int sum[mxn],prime[mxn],vis[mxn],miu[mxn];

inline int read(){
    int ret = 0,fl = 1;
    char c = getchar();
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void get_mu(int N){
    miu[1] = 1;
    for(int i = 2;i <= N;++i){
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))break;
            else miu[i * prime[j]] = -miu[i];
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];
}

int main(){
    N = read();
    get_mu(50000);
    for(int i = 1;i <= N;++i){
        int a,b,k;
        long long ans = 0;
        a = read();b = read();k = read();
        int limit = min(a,b);
        for(int l = 1,r;l <= limit;l = r + 1){
            r = min(a/(a/l),b/(b/l));
            ans += 1ll * (a/(l * k)) * (b/(l * k)) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

參考文檔

知乎-莫比烏斯反演
數(shù)論初步

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

POI 2007 ZAP - 莫比烏斯反演

POI 2007 ZAP - 莫比烏斯反演

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

POI 2007 ZAP - 莫比烏斯反演

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av